Trees

BST Insert

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

Algorithm

Basic Implementation

basic.kt 
class Node(val value: Int, var left: Node? = null, var right: Node? = null)
fun render(node: Node?): String {
    if (node == null) return "_"
    if (node.left == null && node.right == null) return node.value.toString()
    return "${node.value}(${render(node.left)},${render(node.right)})"
}
fun sampleTree() = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")
fun insert(root: Node?, value: Int): Node { if (root == null) return Node(value); if (value < root.value) root.left = insert(root.left, value) else root.right = insert(root.right, value); return root }
fun main() { var root: Node? = null; for (value in listOf(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

  • Kotlin represents nodes with class Node(val value: Int, var left: Node? = null, var right: Node? = null), so the stored value is immutable but child links are nullable and mutable.
  • main starts with var root: Node? = null and assigns root = insert(root, value) for each value, allowing the first insert to replace the null root with a new node.
  • insert(root: Node?, value: Int): Node allocates Node(value) only when the current subtree root is null; otherwise it mutates root.left or root.right and returns the same root reference.
  • The comparison branch is if (value < root.value) ... else ..., so equal values would follow the right-child path in this implementation.
  • Recursive calls write the returned subtree back into the nullable child slot: root.left = insert(root.left, value) or root.right = insert(root.right, value).
  • The trace inserts 4, 2, 6, 1, 3, 5, 7, producing 4(2(1,3),6(5,7)); it also records a sorted-insert contrast 1(_,2(_,3(_,4))) with height 4.
  • render(root) prints _ for null children and 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.