Trees

How bst insert works

A binary search tree keeps one promise everywhere: everything in a node's left subtree is smaller, everything right is larger. Insertion just follows the promise — compare, go left or right, repeat until you fall off the tree, and that hole is where the new node belongs. No rebalancing, no shifting: one node pointer changes.

The tree's shape is the insertion history. Values arriving in shuffled order build a bushy tree of height ≈ log n; the same values arriving sorted build a chain — every insert goes right, and the “tree” degenerates into a linked list with O(n) operations. Watch it happen: set the values yourself in increasing order and the tree falls over sideways.

That degenerate case is why balanced trees exist (AVL, red-black) — same invariant, plus rotations that cap the height at O(log n). In interviews you rarely implement rotations, but you are expected to know why the worst case is O(n) and what fixes it. Note the duplicate policy too: this version ignores them; alternatives count occurrences or lean right — say which you chose.

space play / pause · ←→ step