Trees & Binary Search Trees

Trees are where data structures stop being linear, and the payoff is immediate: a structure of $n$ nodes can be searched in $O(\log n)$ time instead of $O(n)$, provided its height stays logarithmic.

That proviso is the entire subject. A binary search tree gives $O(h)$ operations where $h$ is the height, and $h$ can be anywhere from ${\log }_{2}n$ to $n-1$ depending on the insertion order. Everything from AVL trees to B-trees exists to force $h$ to stay near its minimum.

Almost every tree question is one of two things. Either a counting argument relating the number of nodes to the height, or a traversal that visits nodes in a specific order.

The counting arguments all come from the same observation: level $i$ of a binary tree holds at most $2^i$ nodes, so a tree of height $h$ holds at most $2^{h+1}-1$.

The traversals all come from one observation too: a recursive traversal visits a node either before, between or after its two recursive calls, and those three placements are the only difference between preorder, inorder and postorder.

A convention must be fixed and stated, because both appear. Throughout this chapter, height is measured in edges, so a single node has height 0 and an empty tree has height $-1$. Some sources count nodes instead, giving answers one larger.

1. Counting Nodes and Heights

A tree with $n$ nodes has exactly $n-1$ edges, because every node except the root has exactly one parent edge.

For a binary tree of height $h$ measured in edges:

$\text{maximum nodes}=2^{h+1}-1\text{minimum nodes}=h+1$

The maximum is achieved by a perfect tree with every level full; the minimum by a degenerate tree that is effectively a linked list.

Inverting the maximum gives the minimum possible height for $n$ nodes:

$h_{\min }=\lceil {\log }_2(n+1)\rceil -1$

A strictly binary tree — one where every node has 0 or 2 children — satisfies a useful identity. If it has $i$ internal nodes then it has exactly $i+1$ leaves, so its total node count is always odd.

The identity generalises. In any binary tree, the number of nodes with two children is exactly one less than the number of leaves.

The number of structurally distinct binary trees with $n$ nodes is the $n$-th Catalan number:

$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$

giving 1, 1, 2, 5, 14, 42 for $n=0$ through 5. The same count applies to binary search trees on $n$ distinct keys, because the shape determines the tree once the keys are fixed.

2. Traversals

Three depth-first traversals differ only in where the node's own visit sits relative to its two recursive calls.

Each has a characteristic use. Preorder produces a prefix expression and is the order in which a tree is copied or serialised, since a node is emitted before its children. Postorder produces a postfix expression and is the order in which a tree is deleted, since children are freed before their parent.

Inorder is the important one for search trees: applied to a binary search tree it visits the keys in sorted order, and this single fact underlies most BST questions.

Level-order traversal visits nodes level by level and is not recursive. It uses a queue: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children.

The contrast is worth stating: depth-first traversals use a stack, explicitly or through recursion, while level-order uses a queue. That is the only structural difference between them, exactly as with graph search.

3. Reconstruction from Traversals

Given two traversals, can the tree be recovered uniquely? The answer depends on which two.

Inorder plus preorder determines the tree uniquely. The first element of the preorder is the root; locating it in the inorder splits the remaining keys into the left and right subtrees; recurse on each part.

Inorder plus postorder also determines it uniquely, using the last postorder element as the root instead.

Preorder plus postorder does not. Without inorder there is no way to tell which subtree is which when a node has only one child, so any node with a single child could have it on either side.

The exception is worth knowing: for a strictly binary tree, preorder plus postorder does determine the tree, because no node has exactly one child and the ambiguity cannot arise.

Inorder alone determines nothing, since every binary search tree on the same key set has the same inorder traversal — the sorted sequence.

4. Binary Search Trees

A binary search tree maintains the invariant that every key in a node's left subtree is smaller than the node's key, and every key in the right subtree is larger.

The invariant is about entire subtrees, not just immediate children, and questions are built by presenting a tree that satisfies the weaker child-only condition and asking whether it is a valid BST.

Search descends from the root, going left or right by comparison, and stops on a match or a null pointer. Every operation costs $O(h)$, and since $h$ ranges from ${\log }_{2}n$ to $n-1$, the same operation can be logarithmic or linear.

Inserting keys in sorted order produces the worst case: each new key is larger than everything present, so it becomes the right child of the previous one and the tree degenerates into a list.

Deletion has three cases, and the third is the one examined.

A leaf is removed directly. A node with one child is replaced by that child. A node with two children is replaced by its inorder predecessor or successor, whose value is copied into the node, and that predecessor or successor is then deleted — a case that has at most one child, so the recursion terminates.

The inorder successor of a node with a right subtree is the leftmost node of that subtree, and the inorder predecessor is the rightmost node of the left subtree.

5. AVL Trees

An AVL tree keeps the height logarithmic by enforcing a local balance condition.

The balance factor of a node is the height of its left subtree minus the height of its right subtree, and it must be $-1$, $0$ or $+1$.

Insertion or deletion can violate this at some node, and the violation is repaired by a rotation. Four cases exist, named by the direction of the two steps from the unbalanced node down to the newly inserted node.

A single rotation fixes the outer cases; the inner cases need two. The reason is that an inner insertion moves the node that must become the new root into a grandchild position, and one rotation cannot promote it far enough.

Rebalancing after an insertion requires at most one rotation — single or double — because the rotation restores the subtree's original height and no ancestor's balance changes. Deletion may require rotations all the way to the root, because a rotation can shorten a subtree and propagate the imbalance upward.

The minimum number of nodes in an AVL tree of height $h$ satisfies a Fibonacci-like recurrence:

$N(h)=N(h-1)+N(h-2)+1$

with $N(0)=1$ and $N(1)=2$. Because this grows exponentially, the height of an AVL tree with $n$ nodes is $O(\log n)$ — approximately $1.44{\log }_{2}n$ in the worst case.

6. Multiway Search Trees

When the data lives on disk rather than in memory, the cost model changes: a disk access costs vastly more than a comparison, so the goal becomes minimising the number of nodes visited rather than the number of comparisons.

A B-tree of order $m$ stores up to $m-1$ keys and $m$ children per node, and every leaf sits at the same depth. Making a node the size of a disk block means one disk read brings in many keys, and the height falls to roughly ${\log }_{m}n$.

A B+ tree stores all data in the leaves and uses internal nodes only as an index, with the leaves linked together. This makes a range scan a single traversal of the linked leaves rather than a repeated descent, which is why database indexes use B+ trees rather than B-trees.

A red-black tree is an alternative balanced binary tree with a weaker balance condition than AVL. It permits a taller tree — up to $2{\log }_2(n+1)$ — but performs fewer rotations on modification, which makes it preferable when updates are frequent and AVL preferable when lookups dominate.

7. Worked Examples

Example 1. A binary tree has 20 leaves and every internal node has exactly two children. How many nodes does it have in total?

For a strictly binary tree, the number of leaves is one more than the number of internal nodes.

So $L=I+1$ gives $20=I+1$, and $I=19$.

The total is $n=I+L=19+20=39$ nodes.

The identity is worth deriving rather than memorising. Each internal node contributes 2 edges, so there are $2I$ edges. Every node except the root has exactly one parent edge, so there are $n-1$ edges. Equating: $2I=I+L-1$, which gives $L=I+1$.

Example 2. The preorder traversal of a binary tree is A B D E C F and the inorder is D B E A C F. Reconstruct the tree and give its postorder.

The first preorder element is the root, so A is the root.

Locate A in the inorder: D B E | A | C F. Everything to the left, D B E, forms the left subtree; everything to the right, C F, forms the right subtree.

The preorder after A is B D E C F, so the next 3 elements B D E describe the left subtree and the remaining C F the right.

For the left subtree, preorder B D E and inorder D B E. Root is B, with D on the left and E on the right — both leaves.

For the right subtree, preorder C F and inorder C F. Root is C. In the inorder, nothing precedes C, so its left subtree is empty and F is its right child.

The tree has root A, left child B with children D and E, and right child C with right child F.

Postorder visits left, right, then node: D E B F C A.

Note that the right subtree here has a node with a single child, which is exactly the configuration that would make preorder-plus-postorder ambiguous. Inorder is what resolved it.

Example 3. Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST, then delete 30. Show the result.

Insertion places each key by descending from the root.

50 becomes the root. 30 is smaller, so it goes left. 70 is larger, so it goes right. 20 is smaller than 50 and than 30, so it becomes 30's left child. 40 is smaller than 50 but larger than 30, so it becomes 30's right child. 60 is larger than 50 and smaller than 70, so it becomes 70's left child. 80 becomes 70's right child.

The tree is perfectly balanced with height 2.

Now delete 30. It has two children, 20 and 40, so it is the third deletion case.

Replace it by its inorder predecessor, the rightmost node of its left subtree, which is 20. Copy 20 into the node and delete the original 20, which is a leaf.

The result has root 50, left child 20 with right child 40, and right child 70 with children 60 and 80.

Using the inorder successor instead would have given 40 in that position with 20 as its left child, which is equally valid — either choice preserves the invariant, and a question must say which is intended.

Example 4. What is the minimum number of nodes in an AVL tree of height 5?

Use the recurrence $N(h)=N(h-1)+N(h-2)+1$, which says that a minimal tree of height $h$ has a root plus minimal subtrees of heights $h-1$ and $h-2$ — the most unbalanced arrangement the AVL condition permits.

$N(0)=1$, a single node. $N(1)=2$, a root with one child. $N(2)=N(1)+N(0)+1=2+1+1=4$. $N(3)=N(2)+N(1)+1=4+2+1=7$. $N(4)=N(3)+N(2)+1=7+4+1=12$. $N(5)=N(4)+N(3)+1=12+7+1=20$.

The minimum is 20 nodes.

The sequence 1, 2, 4, 7, 12, 20 is each Fibonacci number minus one, which is why the growth is exponential and the height stays logarithmic. For comparison, an unbalanced binary tree of height 5 needs only 6 nodes.

Example 5. Inserting 10, 20, 30 into an empty AVL tree causes an imbalance. Identify the case and perform the rotation.

Insert 10: it becomes the root, balance factor 0.

Insert 20: larger, so it becomes the right child. The root's balance factor is $0-1=-1$, which is permitted.

Insert 30: larger than both, so it becomes 20's right child. Now the root has an empty left subtree of height $-1$ and a right subtree of height 1, giving a balance factor of $-1-1=-2$. The condition is violated at the root.

Trace the path from the unbalanced node to the new node: right, then right. This is the RR case, fixed by a single left rotation about the unbalanced node.

The rotation makes 20 the new root, with 10 as its left child and 30 as its right child.

Every balance factor is now 0 and the height has fallen from 2 to 1.

Had the insertions been 10, 30, 20 instead, the path would have been right then left — the RL case — requiring a right rotation about 30 followed by a left rotation about 10, and arriving at the same final tree.

Example 6. How many structurally distinct binary search trees can be built from the keys 1, 2, 3, 4?

The number of distinct binary tree shapes on $n$ nodes is the $n$-th Catalan number, and for a BST the shape determines the tree completely, since the key placement is forced by the ordering invariant.

$C_4=\frac{1}{5}\left(\genfrac{}{}{0ex}{}{8}{4}\right)=\frac{1}{5}\times 70=14$

There are 14 distinct binary search trees.

The recursive derivation is worth seeing. Choosing key $k$ as the root forces the $k-1$ smaller keys into the left subtree and the $4-k$ larger keys into the right, so the count is the sum over $k$ of $C_{k-1}\times C_{4-k}$.

That is $C_0{C}_3+C_1{C}_2+C_2{C}_1+C_3{C}_0=1(5)+1(2)+2(1)+5(1)=5+2+2+5=14$, confirming the closed form.

Note the contrast with plain binary trees on 4 labelled nodes, where the labels can be permuted and the count is $14\times 4!=336$. The BST invariant removes that freedom entirely.

Summary

Height is measured in edges here: a single node has height 0. Sources counting nodes give answers one larger, so the convention must be checked.

A tree with $n$ nodes has $n-1$ edges. A binary tree of height $h$ holds between $h+1$ and $2^{h+1}-1$ nodes, so the minimum height for $n$ nodes is $\lceil {\log }_2(n+1)\rceil -1$.

A strictly binary tree has one more leaf than internal nodes. The number of distinct binary trees on $n$ nodes is the Catalan number.

Preorder, inorder and postorder differ only in where the node's visit sits relative to the two recursive calls. Level-order uses a queue where the others use a stack.

Inorder traversal of a BST gives sorted order, which is the fact most BST questions rest on.

Inorder with either preorder or postorder reconstructs a tree uniquely; preorder with postorder does not, except for strictly binary trees.

The BST invariant constrains entire subtrees, not just immediate children. Operations cost $O(h)$, and sorted insertion produces the degenerate linear case.

Deleting a two-child node replaces it with the inorder predecessor or successor, which has at most one child.

An AVL tree keeps every balance factor in $\{-1,0,+1\}$. Outer imbalances need one rotation and inner ones need two. Insertion needs at most one rotation; deletion may need rotations up to the root.

The minimum AVL node count follows a Fibonacci-like recurrence, which forces the height to $O(\log n)$.

B-trees and B+ trees trade comparisons for disk accesses by widening nodes, and B+ trees additionally link the leaves so that range scans need no re-descent.