Binary trees & BSTs

A binary tree is built from nodes, like a linked list, but each node has two references instead of one: left and right. Either can be nothing. One node, the root, is where everything starts; every other node hangs below exactly one parent. A node with no children is a leaf.

A node together with everything below it is a subtree. Every node's left child starts its left subtree and its right child starts its right subtree, so most tree code is recursive: do something at this node, then hand each subtree to the same function.

In the pseudocode, TreeNode(x) makes a node holding x whose left and right are nothing.

A binary search tree (BST) is a binary tree with one rule about where values go. The tree above follows it: 8's left subtree holds 1, 3, 4, 6 and 7, all smaller than 8, and its right subtree holds 10 and 14, both larger. The same is true at 3, at 6 and at every other node.

That rule is binary search, built into the shape. Comparing with one node tells you which half of the remaining values can hold the one you want, and the other half is never looked at. Read the nodes from left to right and they come out sorted.

To find 7, compare it with the root. Smaller goes left, larger goes right, equal means found. Running off the tree into nothing means the value isn't there.

Four comparisons for a tree of eight values. The work is one step per level, so the cost is O(h), where h is the number of levels.

Inserting is a search that is expected to fail. Walk down exactly as if looking for the new value; when the next step would go to nothing, that empty spot is the only place the value can go without breaking the rule. Hang a new node there. No existing node moves.

The new value always ends up as a leaf. That is also why the order of inserts decides the shape: the first value inserted stays the root for good.

Deleting a leaf is easy: its parent forgets it. A node with one child is nearly as easy: the child moves up into its place. A node with two children is the hard case, because two subtrees can't both hang from its parent's one slot.

The fix: find the next larger value in the tree, the leftmost node of the right subtree, and copy it over the value being deleted. Everything on the left is still smaller, and everything that remains on the right is still larger. The node the value came from has no left child, so removing it is one of the easy cases.

The recursion returns each subtree's new top, and every caller stores it back with node.left ← … or node.right ← …. That one habit handles all three cases, including deleting the root.

Search, insert and delete each follow one path from the root, so all three are O(h). How big h is depends entirely on the order the values arrived in:

A full tree with 20 levels holds 2²⁰ − 1 = 1,048,575 values, so a million values can fit in 20 levels, and every operation costs about 20 comparisons. Insert the same million values in sorted order and the tree is a chain a million levels deep: every operation is a linear search. Sorted input is common in practice, so a plain search tree is a risk. Balanced trees keeps the tree bushy whatever the order.