Topic 9 of 20
Recursive DFS, level-order BFS, path problems, construction and lowest common ancestors.
A binary tree is a recursive structure: every node has a value and up to two subtrees. Because of that, most tree problems have short recursive solutions once you decide what each call should return. Ask "if I knew the answer for my left and right subtrees, how would I compute mine?". That is bottom-up DFS, and it solves height, diameter, balance and maximum path sum.
Sometimes information must flow downward instead, such as the path so far, the current depth, or the maximum seen on the way down. That is top-down DFS, where you pass state as parameters. For anything described in terms of levels (right side view, zigzag order, width), use BFS with a queue and process one level at a time.
Learn the three traversal orders both recursively and iteratively, then practise construction from traversals, lowest common ancestor and serialisation. Trees are the most frequently tested data structure in FAANG interviews, and the skills here carry directly into BSTs, heaps, tries and graphs.
Recursive and iterative inorder; the stack version is asked often.
Preorder with an explicit stack.
Postorder is the order bottom-up solutions naturally follow.
The simplest bottom-up recursion.
BFS stops at the first leaf; shows when BFS beats DFS.
Building a new tree while walking two.
Return height, update a global answer; the key tree trick.
Return height or a failure signal in one pass.
Combines traversal with the same-tree check.
Carrying a remaining sum down to the leaves.
Uses the complete-tree shape to beat O(n).
The standard BFS template for trees.
Level-order BFS with alternating direction.
The last node of each level; asked constantly at Meta.
Carrying the path maximum downward.
Heap-style indexing across a level.
Rebuilding a tree from traversals using an index map.
The same construction from the other direction.
The classic LCA recursion; a top Meta and Amazon question.
Collecting root-to-leaf paths with backtracking.
Prefix sum plus hash map, carried along tree paths.
Building numbers along paths.
In-place restructuring of a tree.
Linking each level using the level above; O(1) extra space.
Adding parent links turns a tree into a graph.
Multi-direction spreading from a node.
Carry the min and max down each path.
Dynamic programming on a tree: return a (take, skip) pair.
The flagship Hard tree problem.
Encoding a tree as a string; a very common design-style question.
Coordinates plus custom sorting.