Topic 9 of 20
Binary Trees
Recursive DFS, level-order BFS, path problems, construction and lowest common ancestors.
The concept
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.
Patterns you will learn
Problems, in order
- 1
Recursive and iterative inorder; the stack version is asked often.
DFS Traversals (Pre / In / Post)Reported at: AmazonMicrosoftApple+1 - 2
Preorder with an explicit stack.
DFS Traversals (Pre / In / Post)Reported at: GoogleAdobe - 3
Postorder is the order bottom-up solutions naturally follow.
DFS Traversals (Pre / In / Post)Reported at: Meta - 4
The simplest bottom-up recursion.
Bottom-up DFS (Return Values)Reported at: GoogleAmazonMicrosoft+5 - 5
BFS stops at the first leaf; shows when BFS beats DFS.
BFS Level OrderReported at: MetaBloomberg - 6
- 7
- 8
- 9
Building a new tree while walking two.
Parallel DFSReported at: MetaAmazonUber - 10
Return height, update a global answer; the key tree trick.
Bottom-up DFS (Return Values)Reported at: MetaAmazonGoogle+3 - 11
Return height or a failure signal in one pass.
Bottom-up DFS (Return Values)Reported at: AmazonGoogleMeta+2 - 12
Combines traversal with the same-tree check.
DFS + Tree ComparisonReported at: AmazonMetaMicrosoft+1 - 13Path SumEasy
Carrying a remaining sum down to the leaves.
Top-down DFS (Carry State)Reported at: MetaMicrosoftAmazon+2 - 14
Uses the complete-tree shape to beat O(n).
Binary Search on TreeReported at: GoogleAmazonByteDance / TikTok - 15
The standard BFS template for trees.
BFS Level OrderReported at: AmazonMicrosoftMeta+6 - 16
Level-order BFS with alternating direction.
BFS Level OrderReported at: AmazonMetaMicrosoft+6 - 17
The last node of each level; asked constantly at Meta.
BFS Level OrderReported at: MetaAmazonApple+5 - 18
Carrying the path maximum downward.
Top-down DFS (Carry State)Reported at: MicrosoftSalesforce - 19
Heap-style indexing across a level.
BFS with IndicesReported at: AmazonGoogleMeta+2 - 20
Rebuilding a tree from traversals using an index map.
Tree ConstructionReported at: MicrosoftGoogleAmazon+3 - 21
The same construction from the other direction.
- 22
The classic LCA recursion; a top Meta and Amazon question.
Lowest Common AncestorReported at: MetaAmazonMicrosoft+4 - 23Path Sum IIMedium
Collecting root-to-leaf paths with backtracking.
Top-down DFS + BacktrackingReported at: AmazonMetaGoogle+2 - 24Path Sum IIIMedium
Prefix sum plus hash map, carried along tree paths.
Prefix Sum on Tree PathsReported at: MetaGoogleByteDance / TikTok+1 - 25Sum Root to Leaf NumbersMedium
Building numbers along paths.
Top-down DFS (Carry State)Reported at: MetaMicrosoftAmazon - 26
In-place restructuring of a tree.
Reverse Postorder / MorrisReported at: MetaAmazonMicrosoft+1 - 27
Linking each level using the level above; O(1) extra space.
- 28
Adding parent links turns a tree into a graph.
- 29
Multi-direction spreading from a node.
- 30
Carry the min and max down each path.
Top-down DFS (Carry State)Reported at: AmazonGoogleMeta - 31House Robber IIIMedium
Dynamic programming on a tree: return a (take, skip) pair.
Tree DPReported at: AmazonGoogleAdobe - 32
The flagship Hard tree problem.
Bottom-up DFS (Return Values)Reported at: AmazonMetaMicrosoft+8 - 33
Encoding a tree as a string; a very common design-style question.
SerializationReported at: AmazonMicrosoftGoogle+6 - 34
Coordinates plus custom sorting.
BFS/DFS with Coordinates + SortingReported at: MetaAmazonMicrosoft+2 - 35