Binary search tree BST

Look at what the two earlier structures are good at. A sorted array searches very quickly: binary search halves the range each time, O(log n). But inserting a new value means making room for it, and every element to its right moves one position, O(n). A linked list is the opposite. Once you already hold the position, linking a node in changes two pointers, O(1). Finding a value, though, means walking from the head, O(n). A linked list cannot even run binary search, because it has no O(1) random access: the step "jump to the middle" itself costs O(n).

The idea of a BST is to freeze the decisions of binary search into the shape of a tree. Think of a library. The sign at the entrance says "A–M left, N–Z right". Inside the left wing another sign says "A–F left, G–M right". Each sign you read removes a large part of the building from your search. Every node of a BST is one of those signs. And because the nodes are connected by pointers (chapter 3), adding a new sign moves nothing that is already there.

The previous chapter covered four traversals. For a BST one of them matters more than the rest: in-order traversal (left → node → right) always outputs the keys in ascending order. Why? Draw the tree with each node above its own position on the line below. The rule puts every node of the left subtree left of the root and every node of the right subtree right of it, so the horizontal position of a node is its rank in sorted order:

How is this used? Read it in both directions. To get the data out of a BST in order, traverse in order; no sorting step is needed. To check whether a tree is a BST, check that its in-order sequence is strictly increasing. To find the k-th smallest value, count to k during an in-order traversal. One property carries half of this chapter's problems.

Now search. Type a number into the lab below and press Search. It starts at the root, and after each comparison it continues on one side only. Try Insert as well: the new value always ends up in the empty slot where the search failed. Then press "Insert 1→5 in order" at least once and watch a tree that still obeys the rule but has lost all its speed.

Why O(h) everywhere and not O(log n)? Because h, the height of the tree, is a variable. As in chapter 7, height is the number of edges on the longest root-to-leaf path, so a tree with only a root has height 0. When the tree is balanced, h = ⌊log₂n⌋, since each level can hold twice as many nodes as the one above it. When sorted input makes the tree degenerate into a chain, h = n − 1. Saying O(log n) without a condition is wrong. The complete answer is: O(h); that is log n when the tree is balanced and n in the worst case, and production code uses a red-black tree to keep h at log n.

You have already done search and insert by hand in the lab. The hard operation is delete. Removing a node leaves a hole in the tree, and the hole has to be filled without breaking the ordering. Split it by how many children the deleted node has:

Case 3 raises two questions worth answering. Why can the successor take the place? The in-order successor is the next key above the deleted one, with nothing in between. After it moves up, every node on the left is still smaller than it (it is larger than the deleted value), and every remaining node on the right is still larger than it (it was the smallest value there). The ordering holds on both sides, and no other key would do. Why is deleting the successor easy? The successor is the end of a walk left from the right child, so it has no left child. Deleting it falls into case 1 or case 2, and the recursion cannot continue for ever. The in-order predecessor (the largest value in the left subtree) works the same way, by symmetry.

The node is the TreeNode from the binary tree chapter: a value plus a pointer to each child. Of the four methods, insert and delete are written recursively, and both return the root of the repaired subtree so the caller can reattach it. This pattern — return yourself so the parent links to you again — is the standard way to modify a tree by recursion, and it avoids having to track parent pointers.

The lab in §02 showed it already: sorted input grows a BST into a chain. Real data is often sorted: log records written by timestamp, rows inserted by auto-increment id, word lists imported alphabetically. A plain BST will almost certainly degenerate in production. The idea behind the fix is direct: after an insert or a delete, if some part of the tree has become too deep on one side, rotate it back. Balanced trees differ only in how they define "too deep" and how far they let it go before acting.

AVL (1962, named after its inventors Adelson-Velsky and Landis) gives every node a balance factor: the height of the left subtree minus the height of the right subtree. It requires that factor to stay in {-1, 0, 1} for every node. As soon as an insert pushes some node to |BF| = 2, a rotation repairs it. Here is the smallest example, inserting 3, 2, 1 in that order:

A real AVL also handles the "left-right" and "right-left" shapes, which need two rotations. The idea is the same: bring the middle of the three values up to be the root. AVL is the strict option. Its height stays close to log n, so lookups are as fast as they can be. The price is paid on writes.

A red-black tree takes a different route. Instead of watching the height difference, it gives each node a color and keeps five rules:

• 1. Every node is either red or black.
• 2. The root is black.
• 3. Empty positions (the null children) count as black.
• 4. The children of a red node must be black, so two reds can never be adjacent.
• 5. From any node, every path down to an empty position contains the same number of black nodes.

Together these give a neat result. The longest path can only alternate red and black, the shortest path can be all black, and both contain the same number of black nodes by rule 5. Therefore the longest path is at most twice the shortest, and the height stays in O(log n). The tree is allowed to be somewhat uneven, and in exchange each update needs only a small fixed number of rotations: at most 2 for an insert and at most 3 for a delete. An AVL insert also needs at most one rotation, but an AVL delete may have to rebalance at every level on the way back to the root. Not perfectly balanced, just balanced enough — that is an engineering trade-off, and it is why the red-black tree ended up in the standard libraries. Use AVL when reads dominate; use red-black when reads and writes are mixed.

One question decides whether you want a tree at all: do you need order? For a plain lookup — is this key present, what is its value — a hash table wins, because it is O(1) on average and a tree is O(log n). You choose a balanced BST when the requirement mentions range queries, the nearest key above or below a value, or iterating in key order. A hash table cannot answer any of those without reading everything and sorting it.

Most BST problems fall into three patterns. First, use in-order = sorted (k-th smallest, minimum difference, validation, recovery). Second, use the comparison to drop a subtree (search, insert, delete, lowest common ancestor, pruning a range sum). Third, build in reverse (turn sorted data into a balanced BST). The three walkthroughs below take one pattern each.

The task: decide whether a binary tree is a valid BST. The trap: almost everyone first writes "check that each node is larger than its left child and smaller than its right child". That is wrong. The rule covers the whole subtree, not one parent and its children. Here is the counterexample built to break it:

The task: return the k-th smallest value in a BST. The brute force: traverse in any order, collect every value, sort, take the k-th. That is O(n log n) and uses nothing about the BST. Why in-order: the sorting was already done when the tree was built. In-order traversal is the values in ascending order, so you only have to count as you go and stop at k:

The task: turn an ascending array into a height-balanced BST. What not to do: insert the elements one by one. The input is sorted, and the lab in §02 showed what that produces: a chain. The solution: balance means the two sides hold almost the same number of nodes, and in a sorted array it is obvious which value belongs in the middle. Take the midpoint as the root, and build the two halves recursively.