Module 16
Binary Trees
Recursion on structure: depth-first orders, level-by-level BFS, returning values up the tree, and building trees from traversals.
A binary tree is recursion made visible: every node is the root of a smaller tree. Most tree problems become short once you decide what each call should return to its parent, and whether you need information from the children (post-order) or must pass information down (pre-order).
This module covers the vocabulary, the four traversals, breadth-first search by levels, the "return a value, update a global answer" pattern behind diameter and path sums, and constructing trees from traversal orders. Each dry run draws the actual tree.
Best after: Recursion, Queue, Deque and Monotonic Queue
Part 1
Learn the ideas
- 16.1Tree Vocabulary and TreeNodeRoot, children, leaves, depth, height: the words every tree problem uses, and the TreeNode class behind them.12 min
- 16.2Depth-First Traversals: Pre, In and Post OrderThe three DFS orders differ only in when you visit the node: before its children, between them, or after them.14 min
- 16.3Breadth-First: Level by LevelA queue processes the tree one level at a time; read the queue's size at the start of each level.12 min
- 16.4Returning Values Up the TreeEach call returns one thing to its parent (like height), while a separate variable records the best answer seen anywhere (like the diameter).14 min
- 16.5Building Trees from TraversalsPre-order gives you the root first; in-order tells you which values are in the left and right subtrees. Together they rebuild the tree.12 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
The simplest post-order recursion: depth = 1 + the deeper subtree.
Changing a tree's structure recursively: swap the children of every node.
Recurse on two trees at once, comparing structure and values.
Compare a tree with its own mirror: outer children with outer, inner with inner.
Return height to the parent; record left + right as the best path through each node.
Return a sentinel (−1) up the tree as soon as a subtree is unbalanced, keeping it O(n).
The BFS template with level sizes.
Per-level answers from BFS: the last node of each level is what you see from the right.
Pass information down (the remaining sum) and check at the leaves.
Post-order signals: each subtree reports whether it found p or q; the first node with reports from both sides is the LCA.
Divide and conquer on traversals: the root splits the in-order list, and a hash map makes it O(n).
Kadane's idea on a tree: each node returns its best one-sided gain (ignoring negative branches) and records the best two-sided path.