Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Scala DSA implementation can be compared directly with the rest of the DSA track.

binary search tree Values smaller than a node go left; larger values go right.

Visual walkthrough

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Basic Implementation

basic.scala 
import scala.collection.mutable.{ArrayBuffer, Queue}
class Node(val value: Int, var left: Node = null, var right: Node = null)
object Main {
  def render(node: Node): String = {
    if (node == null) "_"
    else if (node.left == null && node.right == null) node.value.toString
    else s"${node.value}(${render(node.left)},${render(node.right)})"
  }
  def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))
  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
  def insert(root: Node, value: Int): Node = { if (root == null) return new Node(value); if (value < root.value) root.left = insert(root.left, value) else root.right = insert(root.right, value); root }
  def main(args: Array[String]): Unit = { var root: Node = null; for (value <- List(4, 2, 6, 1, 3, 5, 7)) root = insert(root, value); println(render(root)) }
}

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • class Node(val value: Int, var left: Node = null, var right: Node = null) stores an immutable node value and mutable child references.
  • This source uses null for empty child links rather than Option[Node].
  • insert(root: Node, value: Int): Node handles an empty subtree first: if (root == null) return new Node(value).
  • For an existing node, value < root.value recurses left and assigns root.left = insert(root.left, value); otherwise it assigns root.right = insert(root.right, value).
  • Equal values would follow the else branch to the right, though the checked insert list has no duplicates.
  • var root: Node = null is reassigned after each call so the first inserted node becomes the tree root.
  • The trace inserts 4, 2, 6, 1, 3, 5, 7, showing paths like 4 -> left -> 2 -> right before reaching 4(2(1,3),6(5,7)).
  • The replay also includes a sorted-order contrast: [1, 2, 3, 4] forms 1(_,2(_,3(_,4))), a height-4 chain with no rotation.
  • render(node) prints _ for null children and nested value(left,right), so println(render(root)) outputs 4(2(1,3),6(5,7)).