Trees

Learning Roadmap

Solid arrows are prerequisites - master the source before the target. Phase 1 and 2 are the whole interview surface; Phase 3 is the rest of the family, and you can read those in any order once the first two are solid.

Phase 1 · Foundations

Phase 2 · Core Patterns

Phase 3 · The Tree Family

Tree Anatomyroot · leaf · depth vs height · full · complete · perfect · degenerateRepresentationTreeNode · [1,null,2] · heap array · edgesDFS Traversalone walk, three visit slotsLevel Orderqueue · the level fenceTop-Down Recursionpass context to the childrenBottom-Up Recursionfold what the children returnedThe Two-Answers Patternreturn a height, record a diameterPaths & Backtrackingappend, recurse, popBinary Search Treesthe subtree-range invariantKeeping It Balancedrotations · AVL · red-black · B-treeHeapscomplete tree in an arrayTriesthe key lives on the pathRange Query Treessegment tree · Fenwick · lazyN-ary Treeschildren list · no inorderTrees as Graphsedge list · diameter · rerootingTrees in the WildB+ trees · the DOM · git

prerequisite

Learn

• Tree Anatomy - the vocabulary, drawn out: root, parent, sibling, leaf, ancestor, subtree, depth versus height; then full, complete, perfect, balanced, degenerate, n-ary, and the height-versus-node-count arithmetic behind every O(log n) claim. Start here if any tree word has ever been fuzzy, or to understand why the same code is logarithmic on one input and linear on another.
• Representation - TreeNode, the [1,null,2,3] level-order form, the heap array, parent arrays, edge lists, and serialise/deserialise. This is where the "null-padded array is not the heap array" trap lives.
• Traversal and Recursion - one depth-first walk with three visit slots, the iterative forms, level order and the level fence, Morris; then what goes in the slot: the two-blank contract, top-down versus bottom-up, the two-answers pattern, path backtracking, two trees at once, and the accidental quadratics. The page to actually internalise: nearly every tree problem is this walk with one of these shapes in one of the slots.
• Binary Search Trees - the invariant, search/insert/delete, why inorder is sorted, validation done properly, and the degenerate case. The subtree-range invariant is the single most misremembered fact in this section.
• Keeping a Tree Balanced - rotations, AVL, red-black, B-trees, and which one your language actually ships. The answer to "so what if the tree degenerates".
• Heaps & Priority Queues - the heap property, the array packing, sift up and down, linear-time heapify, and heapq in practice. A complete tree with no pointers at all.
• Tries - a tree whose edges are characters, the end-of-word flag, what it costs, and the prefix problems it collapses. Includes the binary trie, which is the interview payoff.
• Range Query Trees - segment trees, lazy propagation, and Fenwick trees. For when queries and updates are both live and prefix sums stop working.
• Trees in the Wild - filesystems, the DOM, B+ trees, LSM trees, and git's Merkle tree. Not needed for interviews; read it to make the rest stick.
• Structural Approach to Tree Concepts - nine specific recursion traps, worked end to end.

Also worth reading:

• Trees as Graphs - what to do when the tree arrives as an edge list and there is no .left or .right.

What do I reach for

The section compressed into one lookup. Read the question, not the tree: the phrasing picks the traversal far more reliably than the input shape does.

The question asks for	Reach for	Cost
"height", "depth of the tree", "diameter", "is it balanced"	bottom-up postorder - Traversal and Recursion	O(n)
"the longest path", and it need not pass the root	the two-answers pattern: return a height, record a best	O(n)
"root-to-leaf", "path sum", "all paths"	top-down with append/pop backtracking	O(n) plus output
"level", "row", "each depth", "side view", "zigzag"	level-order BFS with the len(q) fence - Traversal	O(n)
"minimum depth", "nearest leaf"	BFS, and stop at the first leaf dequeued	O(n) worst, far less typically
"k-th smallest", "sorted", "validate BST"	inorder - Binary Search Trees	O(h + k) / O(n)
"search / insert / delete a value" in a BST	the descent: compare, go left or right	O(h), which is O(n) if it is skewed
"serialise", "clone", "copy", "reconstruct from traversals"	preorder with null markers - Representation	O(n)
"are these two trees the same / symmetric / one a subtree of the other"	lockstep recursion on both, three null cases first	O(n) / O(n * m)
"lowest common ancestor"	one postorder pass returning the first node that sees both sides	O(n), or O(log n) per query with binary lifting
"the k largest / smallest / most frequent", streaming	a size-k heap - Heaps	O(n log k)
"repeatedly take the minimum", "scheduling", "merge k lists"	a heap	O(n log n)
"words with this prefix", "autocomplete", "word search on a board"	a trie	O(L) per word
"maximum XOR pair"	a binary trie over the bits	O(n * 32)
"range sum / min / max with updates"	a segment tree, or Fenwick if it is prefix sums only	O(log n) per op
"range sum", no updates	prefix sums. Do not build a tree.	O(1) per query
the input is n and an edge list of n - 1 edges	root it with a DFS and a parent skip - Trees as Graphs	O(n)
"the longest path in a tree given as edges"	double-sweep BFS for the diameter	O(n)
"the answer for every node as root"	rerooting: one pass down, one pass up	O(n)
n <= 10^5 and the tree might be skewed	the iterative traversal, or an explicit stack	avoids RecursionError

The bug checklist

Every trap on the Learn pages, in roughly the order they tend to bite. If a tree solution is wrong and you do not know why, read down this list.

#	Check	Symptom when wrong
1	Is the base case if not node, rather than a leaf test?	AttributeError on None the first time a node has exactly one child.
2	Is a leaf tested as not node.left and not node.right - both?	Internal nodes leaning one way get counted as leaves. Passes on every symmetric test tree.
3	Height in edges or in nodes? Base case -1 or 0?	Every answer off by exactly one.
4	Level-order: is size = len(q) snapshotted before children are appended?	All levels merge into one flat list. The flat list is still a valid traversal, so it looks fine.
5	Path building: is it out.append(list(path)), not out.append(path)?	The right number of answers, all identical, all empty.
6	Does every path.append have exactly one matching pop, on every exit?	Later branches inherit stale nodes; answers grow monotonically wrong.
7	Two-answers pattern: does the helper return the height and record the through-path separately?	Correct whenever the answer passes the root, wrong when it bends in a subtree.
8	BST validation: is it a (lo, hi) range, not a parent comparison?	Accepts trees that are locally fine and globally not - the standard wrong answer to LC 98.
9	BST: could the input be sorted? Then the tree is a chain.	O(log n) claimed, O(n) delivered; TLE on the large case.
10	Comparing two trees: both-null, one-null, neither-null, in that order?	AttributeError, or two empty trees reported unequal.
11	Is a height being recomputed inside a recursion that already knew it?	Accidental O(n^2). Looks linear, times out on a skewed tree.
12	nonlocal declared for any accumulator the helper assigns to?	UnboundLocalError.
13	Recursion depth: could n exceed about 1000 on a skewed tree?	RecursionError on large but legal input.
14	Heap array: is the tree actually complete? 2i+1 arithmetic on a null-padded LeetCode array?	Children read from the wrong slots; silent nonsense.
15	heapq is a min heap. Did you negate for a max heap, and add a tiebreak to the tuple?	Reversed answers, or TypeError: not supported between instances of ....
16	Trie: is is_word set, rather than inferring a word from having no children?	"cat" present makes "ca" present; prefixes of stored words match as words.

Practice

• Binary Tree - traversal, path and height, views, modification, two-tree comparison, post-order processing.
• Binary Search Tree - traversal and manipulation on the ordered version.
• N-ary Tree - the children-list shape.