Trees

You have already spent an entire Academy level inside a tree without this lesson: the abstract syntax tree of Level 3, where a program's structure branches from one root through nested expressions down to individual literals. Trees are what pointer structures become when each node may reference several successors instead of one, and the family is everywhere: file systems, HTML documents, company org charts, decision processes, and the search structures this lesson builds. The vocabulary is compact and worth locking in once.

• Root: the single node at the top, the only one with no parent.
• Parent and child: each node except the root has exactly one parent; nodes may have any number of children.
• Leaf: a node with no children, where paths end.
• Subtree: any node plus everything below it, itself a complete tree, which is why recursion and trees fit like hand and glove.
• Height: the longest path from root to leaf, the number that decides every cost in this lesson.
• Binary tree: at most two children per node, named left and right.

A family tree drawn upside down is the honest picture: one ancestor at top, generations widening below. What makes trees computationally special is how fast those generations widen. One node has up to 2 children, 4 grandchildren, 8 great-grandchildren: each level can double. Run that in reverse and you get the miracle: a million nodes need only about 20 levels, because doubling reaches a million in 20 steps. Every efficient tree operation is a walk from the root down one path, and short trees make short walks.

Height is everything

A binary tree of height h can hold at most 2 to the power h plus 1, minus 1 nodes, filling every level. Flip the inequality: holding n nodes requires height at least log base 2 of n, roughly. A tree that stays close to that floor is called balanced, and its height is O(log n). Nothing forces balance, though: link the same n nodes each with only a right child and the so-called tree is a linked list wearing a costume, height n. Everything a tree promises depends on which of those two shapes it is in, so watch the doubling deliver a million-node capacity in twenty levels.

The binary search tree

Now give the binary tree a job. A binary search tree, BST, adds one invariant to the shape: at every node, every key in the left subtree is smaller than the node's key, and every key in the right subtree is larger. That single rule turns lookup into a guided descent. Compare your target with the root: smaller means the entire right half of the data is eliminated without a glance, larger eliminates the left. Repeat down the tree, one comparison per level, until you hit the key or fall off a leaf. Cost: one comparison per level, O(height), which balanced means O(log n). Insertion is the same descent ending in attaching a leaf; the search lesson will show this is binary search reborn as a data structure, one that additionally supports ordered iteration, range queries, and nearest-key lookups, everything the hash map's scrambling forfeited.

The degenerate case is not exotic bad luck: insert already-sorted keys into a naive BST and every insertion descends to the rightmost node, building exactly the height-n chain, with every operation O(n). Sorted input, the most natural input in the world, is the naive BST's worst case. The repair is the family of self-balancing trees, AVL trees being the classic taught in 6.006: after each insertion or deletion, local restructurings called rotations restore a height guarantee, keeping every operation O(log n) in the worst case, adversarial input included. The engineering pattern deserves notice: pay a constant-factor tax on every write to purchase a worst-case guarantee, the same trade hash tables decline, which is why hash maps are faster on average while ordered trees are safer under hostility.

Walking every node: traversals

Visiting all n nodes is a traversal, O(n), and for binary trees the three classic recursive orders differ only in when the node itself is visited relative to its children. In-order, left then node then right, applied to a BST, yields every key in sorted order, a fact that will quietly matter in the sorting lesson. Pre-order, node first, copies or serializes structures top-down. Post-order, node last, evaluates and deletes bottom-up, children before parents. You have watched these without the names: Level 3's from-AST-to-code lesson is traversal at work, and a compiler emitting bytecode for an expression tree works post-order, computing operands before applying operators.

        50
       /  \
     30    70        in-order:   20 30 40 50 60 70 80
    / \    / \       pre-order:  50 30 20 40 70 60 80
  20  40  60  80     post-order: 20 40 30 60 80 70 50

in-order on a BST reads the keys sorted.

The heap, briefly

One more family member earns a mention because the stacks lesson promised it: the binary heap, the machine behind priority queues. A heap is a complete binary tree, every level full except possibly the last, with a weaker invariant than the BST: each parent merely outranks its children, nothing is said about left versus right. Weaker ordering buys a stronger shape: completeness lets the whole tree live inside a plain array, children of slot i at slots 2i+1 and 2i+2, no pointers at all. The top element is always the extreme; insertion and extraction repair the invariant along one root-to-leaf path, O(log n) each. 6.006 devotes a lecture to heaps, and the sorting lesson will meet them again as heapsort.

Trees in protected code

This Academy's relationship with trees is unusually direct: every obfuscator and every deobfuscator is a tree-manipulation program. Source code is parsed into an AST, transformations are rewrites of that tree, renaming walks it, control flow flattening restructures it, and code generation is a traversal that prints it back out. When Level 4 said a transformation must preserve behavior, the precise statement is that the rewritten tree must evaluate identically to the original. Attackers hold the same tools: a decompiler's core loop is recovering a plausible tree from flat instructions, and analysis frameworks pattern-match subtrees the way this lesson matched shapes. If Level 3 taught you what an AST is, this lesson tells you what it costs to walk, rewrite, and search one, and the answer, for balanced structures, is beautifully small.

Trees branch, and branching compounds: height O(log n) when balanced, which puts a million nodes twenty comparisons from the root. The BST invariant turns descent into search and in-order traversal into sorted output, degenerating to O(n) chains without balancing. Heaps trade ordering strength for array-packed completeness and O(log n) priority operations. Every AST you have met is this lesson in costume.

Frequently asked questions