Chapter

Binary Trees

Tree questions look like a catalogue of unrelated puzzles. They are not. Nearly every one is the same three-line walk with a different line in the middle, and this chapter is about the small number of decisions that vary.

Start with the theory6 short chapters, then the problems in order.

Problems

1. Maximum Depth of Binary TreeLC 104 · Post-order · answer built from children
2. Invert Binary TreeLC 226 · Post-order · same walk, different work
3. Binary Tree Level Order TraversalLC 102 · BFS · one row at a time
4. Validate Binary Search TreeLC 98 · Pre-order · pass bounds down
5. Lowest Common Ancestor of a Binary TreeLC 236 · Post-order · report findings upward
6. Construct Binary Tree from Preorder and InorderLC 105 · Divide and conquer · split by the root
7. Binary Tree Maximum Path SumLC 124 · Post-order · return one thing, record another