Binary Trees

A binary tree is defined recursively: it is either empty (denoted $\varnothing$ or `NIL`), or it consists of a root node holding a value, together with a left subtree and a right subtree, each of which is itself a binary tree. This recursive definition is deliberately unlike an ordinary graph-theoretic tree, because it treats "has no left child" and "has no right child" as structurally distinct — a node with only a right child is a different shape from a node with only a left child, even though both have exactly one child. That distinction, absent from general trees, is what makes binary trees so convenient to reason about with recursive algorithms. Standard vocabulary: the parent of a node is the node directly above it; a node with no parent is the root. A node with no children is a leaf (or external node); a node with at least one child is internal. The depth of a node is the number of edges from the root to that node (root has depth 0). The height of a node is the number of edges on the longest downward path from that node to a leaf; the height of the tree is the height of its root. A single-node tree has height 0; the empty tree is conventionally assigned height $-1$ so that the recursive formula $h(T) = 1 + \max(h(T_{\text{left}}), h(T_{\text{right}}))$ holds cleanly even when a subtree is empty. Three shape classifications matter throughout the rest of tree-based data structures:

• A binary tree is full (or "proper") if every node has either 0 or 2 children — no node has exactly one child.
• A binary tree is complete if every level is fully filled except possibly the last, and the last level's nodes are packed as far left as possible.
• A binary tree is perfect if every internal node has exactly 2 children and every leaf is at the same depth.

A perfect tree is always complete and always full. A complete tree need not be full (a node in the last level can have only a left child, making that node degree-1). A full tree need not be complete (a lopsided tree can have every node with 0 or 2 children yet leave gaps in shape). These three notions are logically independent except for the strict implication chain perfect ⟹ complete and perfect ⟹ full; the reverse implications fail. Binary heaps insist on completeness because it lets the tree be stored implicitly in an array; balanced search trees do not insist on completeness, only on height being $O(\log n)$.

There is no single "algorithm" that is a binary tree — it is a data structure, not a procedure — but there is a standard mechanism for representing one and a standard family of recursive procedures that operate on it. The representation uses a node record with three fields: a value, and pointers/references to a left child and a right child, either of which may be null. This is a direct generalization of the singly linked list's one-pointer node to a two-pointer node, and it should feel familiar coming from Linked Lists and Pointers and references. Because the structure is defined recursively, essentially every operation on it is naturally written recursively: compute a size, compute a height, check a shape property, search for a value, or rebuild the tree from a serialization. The pattern is always the same — handle the empty tree as the base case, then combine the results from the left and right recursive calls. ``` struct Node: value left # pointer to Node, or NIL right # pointer to Node, or NIL

# ---- Basic recursive queries ---- function SIZE(node): if node == NIL: return 0 return 1 + SIZE(node.left) + SIZE(node.right) function HEIGHT(node): if node == NIL: return -1 # empty tree has height -1 by convention return 1 + max(HEIGHT(node.left), HEIGHT(node.right))

# ---- Shape classification ---- function IS_FULL(node): if node == NIL: return true if node.left == NIL and node.right == NIL: return true if node.left != NIL and node.right != NIL: return IS_FULL(node.left) and IS_FULL(node.right) return false # exactly one child present: not full function IS_PERFECT(node): return IS_PERFECT_HELPER(node, HEIGHT(node), 0) function IS_PERFECT_HELPER(node, h, depth): if node == NIL: return true if node.left == NIL and node.right == NIL: return depth == h # every leaf must sit at depth h if node.left == NIL or node.right == NIL: return false # internal node must have BOTH children return IS_PERFECT_HELPER(node.left, h, depth + 1) and IS_PERFECT_HELPER(node.right, h, depth + 1)

# ---- Completeness check (level-order / BFS based) ---- function IS_COMPLETE(root): if root == NIL: return true queue = new Queue() queue.push(root) seenNilAfterNode = false # once we see a "gap", no real node may follow while queue is not empty: node = queue.pop_front() if node == NIL: seenNilAfterNode = true else: if seenNilAfterNode: return false # a real node appeared after a gap: not complete queue.push(node.left) # push even if NIL — we need to detect gaps queue.push(node.right) return true ``` `SIZE` and `HEIGHT` walk every node once, combining left and right results — the canonical divide-and-conquer pattern for trees. `IS_FULL` and `IS_PERFECT` similarly recurse, with `IS_PERFECT` additionally threading the tree's height down so every leaf's depth can be checked against it. `IS_COMPLETE` is different in character: completeness is fundamentally a level-by-level ("breadth-first") property, so it is checked using a queue-based traversal that walks the tree level by level, pushing `NIL` placeholders for missing children — the moment a real node shows up after a gap has been recorded, completeness is violated. This level-order idea foreshadows Tree Traversals, where breadth-first and depth-first orders are treated as a topic in their own right.

Space. A binary tree with $n$ nodes uses $O(n)$ space for the nodes themselves, plus $O(n)$ pointers (two per node, some null). No hidden overhead scales worse than linear — this is a direct consequence of the recursive definition, where each node is counted exactly once across the whole structure.

Time for the recursive queries. `SIZE`, `HEIGHT`, and `IS_FULL` each visit every node exactly once and perform $O(1)$ work per node (besides the recursive calls), so each runs in $O(n)$ time and uses $O(h)$ auxiliary stack space, where $h$ is the tree's height — this is the depth of the recursion. In the worst case (a completely lopsided tree, effectively a linked list) $h = n-1$, so the stack usage is $O(n)$; in the best case (a perfect or complete tree) $h = O(\log n)$.

`IS_COMPLETE` complexity. The queue-based check visits each real node once and enqueues at most two `NIL` placeholders per node, giving $O(n)$ time and $O(n)$ worst-case queue space (a perfect tree's last level alone can hold roughly $n/2$ nodes simultaneously in the queue).

The height–node-count relationship — the central fact of this article. Claim (upper bound). A binary tree of height $h$ has at most $2^{h+1}-1$ nodes. Proof sketch by induction on $h$. Base case $h = -1$ (empty tree): $2^{0}-1 = 0$ nodes, correct. Base case $h=0$ (single node): $2^1 - 1 = 1$, correct. Inductive step: a tree of height $h$ has a root plus a left subtree of height at most $h-1$ and a right subtree of height at most $h-1$. By the inductive hypothesis each subtree has at most $2^{h}-1$ nodes, so the whole tree has at most

nodes. Equality holds exactly when the tree is perfect, since that is precisely the condition that both subtrees are themselves full-sized trees of height $h-1$. $\blacksquare$ Claim (lower bound). A binary tree of height $h$ has at least $h+1$ nodes. Proof sketch. The longest root-to-leaf path realizing the height has $h+1$ nodes on it (depths $0,1,\dots,h$), and every node on this path is a distinct node of the tree, so the tree contains at least $h+1$ nodes. Equality holds exactly for a degenerate tree — one where every node has at most one child, i.e., the tree is effectively a linked list bent into tree form. $\blacksquare$

Why this matters for algorithm design. Rearranging the upper bound $n \le 2^{h+1}-1$ gives

meaning a tree cannot be shorter than roughly $\log_2 n$ — but it is entirely free to be as tall as $n-1$. This asymmetry is the whole reason balanced tree structures exist: nothing in the bare definition of "binary tree" prevents height from degenerating to $n-1$, which is exactly what happens if you insert already-sorted keys one at a time into a naive Binary Search Tree. A search, insertion, or deletion that walks root-to-leaf costs $O(h)$, so an unbalanced tree gives $O(n)$ operations — no better than a linked list — while a tree kept close to perfect gives $O(\log n)$ operations. Binary heaps sidestep the whole issue by enforcing completeness on every insertion and deletion, which guarantees $h = \lfloor \log_2 n \rfloor$ at all times; self-balancing search trees (AVL, red-black) enforce a weaker but sufficient invariant that still guarantees $h = O(\log n)$.

Tradeoff to be honest about. Guaranteeing balance is not free: it requires extra bookkeeping (heights or colors stored per node) and rebalancing work (rotations) on every insertion and deletion. A plain unbalanced binary tree is simpler to implement and faster in the average case on random data — but it offers no worst-case guarantee, which is precisely why production systems favor the balanced variants for adversarial or unpredictable workloads.

Consider building a binary tree by inserting the keys `50, 30, 70, 20, 40, 60, 80` in this order, using the ordinary binary-search-tree rule (smaller keys go left, larger keys go right) purely as a way to generate a concrete shape — full BST search semantics are covered in Binary Search Trees.

The resulting tree: ``` 50 / \ 30 70 / \ / \ 20 40 60 80 ``` Trace `HEIGHT(50)`:

• `HEIGHT(50) = 1 + max(HEIGHT(30), HEIGHT(70))`
• `HEIGHT(30) = 1 + max(HEIGHT(20), HEIGHT(40)) = 1 + max(0, 0) = 1`
• `HEIGHT(70) = 1 + max(HEIGHT(60), HEIGHT(80)) = 1 + max(0, 0) = 1`
• `HEIGHT(50) = 1 + max(1, 1) = 2`

Trace `SIZE(50) = 1 + SIZE(30) + SIZE(70) = 1 + 3 + 3 = 7`, matching $n = 7$. Check against the bound: height $h = 2$, so the maximum possible node count is $2^{h+1}-1 = 2^3-1 = 7$. The tree hits the bound exactly — confirming, via the proof above, that this tree must be perfect. Indeed every internal node (50, 30, 70) has exactly two children, and every leaf (20, 40, 60, 80) sits at depth 2. Running `IS_PERFECT` confirms this: at depth 2 every branch bottoms out at a leaf, and `HEIGHT(50) = 2` matches every leaf's depth exactly. Now contrast with inserting the same seven keys already sorted: `20, 30, 40, 50, 60, 70, 80`. Each new key is larger than everything before it, so every node gets only a right child: ``` 20 \ 30 \ 40 \ 50 \ 60 \ 70 \ 80 ``` Here `HEIGHT(20) = 6` and `SIZE(20) = 7` — the same node count as before, but height has jumped from 2 to 6, hitting the lower bound $h = n - 1 = 6$ exactly. This tree is degenerate: `IS_FULL` returns false at the very first node (20 has one child), and a search for `80` now costs 7 comparisons instead of 3. Same data, same number of nodes, wildly different performance — precisely because shape, not size, governs cost.

The binary tree as an abstract data type crystallized alongside the broader development of list processing and symbolic computation in the late 1950s, most directly through work on the LISP programming language, whose core data structure — the cons cell, a pair of pointers — is exactly a binary tree node. The formal analysis of tree height, balance, and search cost was developed through the 1960s and 1970s as computer scientists built the first self-balancing search trees and heap-based priority queues, turning "keep the tree short" from an informal goal into a provable invariant.

Binary trees underlie an enormous share of practical computing infrastructure precisely because of the height-versus-size relationship proven above. Database indexes and filesystem metadata frequently use B-trees and their binary relatives to guarantee logarithmic-time lookups even as data grows into the billions of records. Priority queues used in operating system schedulers, Dijkstra's shortest-path algorithm, and event-driven simulations rely on binary heaps — complete binary trees stored implicitly in arrays, exploiting exactly the shape guarantee discussed here. Compilers represent arithmetic and boolean expressions as expression trees, where a binary tree's recursive structure mirrors the recursive structure of the grammar being parsed. Compression schemes such as Huffman coding build an explicit binary tree whose leaf depths directly encode codeword lengths, again leaning on the height-count relationship to bound compression efficiency. Self-balancing binary search trees (red-black trees, AVL trees) back the standard ordered-map and ordered-set containers found in nearly every major programming language's standard library, from C++'s `std::map` to Java's `TreeMap`. Every one of these systems is, underneath, a careful engineering response to the single fact proved in this article: an unconstrained binary tree can be as tall as $n-1$, and something has to actively fight that possibility to keep operations fast.

Ask the tutor: How exactly do AVL rotations restore the height-balance invariant after an insertion, and why is one or two rotations always enough?