Trees

BST Insert

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

Algorithm

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)) }
}

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

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)).
binary search tree Values smaller than a node go left; larger values go right.