04 — Trees, BSTs and tries

The email names three things here: implement a balanced tree, know how in/pre/postorder differ, and be able to write the traversals in real code. The gap is almost never the recursion — it is the iterative versions and knowing which traversal a problem is asking for.

Prereqs: 01, 09 · Reading: 7 min · Cards: 14 · Code: code/avl.py, code/trie.py

The map

Everything in this topic is one question wearing different clothes: in what order do I visit, and what does each node need to know? Preorder gives the parent before its children, which is what serialising needs. Inorder on a search tree gives sorted order, which is what "k-th smallest" needs. Postorder gives the children before the parent, which is what any "compute something from below" problem needs — and that is the one that arrives in disguise most often.

Layered on top of traversal are three structures. A BST adds an ordering invariant that turns search into O(height). A balanced tree adds rotations that keep the height logarithmic, which is what stops sorted input from degrading it into a linked list. And a trie abandons comparison entirely: the key is the path, not the payload.

What decides your score here

Recognising postorder. Height, diameter, "is it balanced", maximum path sum — none of these prompts mention traversal, and all of them are postorder. Saying "the parent needs a value computed in its children, so this is postorder" before writing is worth more than the code.

Writing an iterative traversal. The recursive versions are assumed. The iterative inorder is what gets asked when the interviewer wants to raise the difficulty, or when depth could exceed Python's recursion limit.

AVL with the rotations, not just the name. The email says "you should know how it's implemented". Four symmetric cases fit in an interview; red-black does not, and you should say so rather than attempting it.

Choosing the traversal

Preorder visits the node, then left, then right. Because the parent comes first, it is what you use to copy or serialise a tree — the reader can build top-down as it consumes tokens.

Inorder visits left, node, right. On a BST that yields the keys in sorted order, which is the entire solution to "k-th smallest" and to validating a BST.

Postorder visits left, right, then the node. Use it whenever the parent's answer depends on results from below.

Level order is BFS with one detail that does all the work: capture the queue length before the inner loop, and everything you dequeue in that pass is exactly one level. Without that line you have a correct BFS and no level boundaries, and half the tree problems ask for the level.

All four are O(n) in time. The space differs and the difference matters: DFS costs O(height) of stack, BFS costs O(width) of queue. In a complete tree the bottom level holds about half the nodes, so BFS can cost linear space where DFS costs logarithmic. On a deep, narrow tree it reverses — and in Python recursive DFS also risks the recursion limit at around a thousand frames.

The iterative inorder, which you should be able to write cold

def inorder_iterative(root):
    out, stack, node = [], [], root
    while node or stack:
        while node:                    # descend to the deepest left
            stack.append(node); node = node.left
        node = stack.pop()
        out.append(node.val)           # visit on the way back up
        node = node.right              # then go right
    return out

Preorder iteratively is simpler — push the root, then pop, visit, and push right before left so left comes off first. Postorder has a trick worth knowing: do node, right, left (a mirrored preorder) and reverse the result at the end.

BSTs, and the mistake everyone makes

The invariant is that every node in the left subtree is smaller than the node, and every node in the right subtree is larger. Search, insert and delete are O(height) — logarithmic if balanced, linear if not.

Validating a BST is where candidates lose the point. Comparing each node only with its immediate parent is wrong: it accepts trees where a deep node violates a distant ancestor's bound. You have to carry a lower and upper bound down the recursion, tightening the upper bound as you go left and the lower bound as you go right. Equivalently, run an inorder walk and check it is strictly increasing — which is a nice one-liner and shows you understand why inorder matters.

Deleting a node with two children has one right answer: replace it with its in-order successor, the smallest node in the right subtree, then delete that successor — which by construction has at most one child.

And the reason balanced trees exist: insert already-sorted keys into a plain BST and you get a linked list. Every operation degrades from logarithmic to linear, on the most ordinary input imaginable.

AVL, because it fits in forty-five minutes

The invariant is that at every node the two subtree heights differ by at most one, which bounds the height at about 1.44 log₂ n.

Four rebalancing cases, and they are two shapes plus their mirrors. Left-left — the imbalance is leftward and the left child leans left — is fixed by one right rotation. Left-right — leftward, but the child leans right — needs a left rotation on the child first, converting it into left-left, then the right rotation. Right-right and right-left are the mirrors.

Implementation with an invariant checker in code/avl.py. Practise drawing one rotation on paper until the pointer updates are automatic; that is what you will be doing in Google Drawings.

The follow-up is always the same: why do the standard libraries use red-black instead? Because AVL is more strictly balanced, so lookups are faster, but it rotates more on every write. Red-black allows a looser balance and does at most three rotations per operation, so its amortised maintenance cost is lower — and real workloads write a lot. That is why std::map, Java's TreeMap and the Linux CFS scheduler all use it. AVL only pays off when reads overwhelmingly dominate.

Python has no balanced tree in the stdlib, because dict and Timsort cover the cases. If pressed: sortedcontainers, which does not even use a tree — it uses lists of lists, and is faster in practice because of cache behaviour.

Tries, where the key is the path

Each node is a prefix and each edge is a character. The word is stored nowhere: it is the path from the root to a node carrying an end-of-word flag. Forgetting that flag is the classic bug — search then returns true for any prefix of a stored word.

Every operation costs O(length of the word), independent of how many words are stored. That independence is the property a hash set cannot match, and it is why tries win for prefix queries (autocomplete), for lexicographic order, and on memory when many words share prefixes. For plain "does this exact key exist", a hash set is faster and simpler, and saying so shows judgement rather than enthusiasm.

N-ary trees are the same traversals with children in a list. Preorder and postorder generalise; inorder does not, because with more than two children there is no defined middle.

Say it

Cover the answers. Out loud, in English.

Now do this

Four problems. The first two build the postorder reflex; the last two are the from-scratch work.

1. Diameter of Binary Tree — 20 min. Say out loud why what you return and what you record are different.
2. Validate BST — 20 min. Bounds, not parent comparison.
3. Binary Tree Level Order Traversal — 15 min. Iteratively, from memory.
4. Implement Trie — 25 min. From scratch, no reference.

Separately, and not on LeetCode: write an AVL insert with all four rotations on paper, then check it against code/avl.py.

Stop when you can write the iterative inorder from memory and draw a left-right rotation without hesitating.