roadmap/Trees

Topic 7 / 16

Trees

MediumNon-Linear~6 days
Moderate
progress0 / 17 solved

Recursive DFS for most problems. BFS (level-order) for layer-by-layer questions.

Concept

Trees are hierarchical graphs with no cycles. Binary trees have at most two children per node. Most tree problems are solved with recursive DFS — the call stack handles the traversal state automatically. BFS (level-order) is best for problems that ask about layers/depths.

When to use this pattern
  • ◆Tree height, depth, diameter
  • ◆Path sum problems
  • ◆Lowest common ancestor
  • ◆Level-order / BFS traversal
  • ◆Validate BST property
  • ◆Serialize / deserialize a tree
Common patterns
Pre-order DFS
Process node before children. Good for cloning, serialization.
Post-order DFS
Process children before node. Good for height, diameter, deletion.
In-order DFS (BST)
Left → node → right gives sorted order in a BST.
BFS / level-order
Queue-based; process all nodes at depth d before depth d+1.
Visual walkthrough
Trees
DFS & BFS Traversals
Left → Root → Right. Gives sorted order for BST.
1234567
current
visited
call stack:inorder(0)
output:[]
Enter node 0 (val=1)
step 1/21
Brute force → optimal thinking
Brute force
Iterative traversal with explicit stack is usually the 'expanded' form.
Observation
Every tree problem decomposes into: what do I do at this node + what do I return from subtrees?
Optimization
Write a recursive helper with a clear return contract. Handle null as the base case. Combine left/right results at each node.
Final complexity
O(n) time — every node visited once. O(h) space for recursion stack where h = height.
Quick Recall Check

Which traversal visits children before the current node?

When is BFS preferred over DFS for tree problems?

What is the space complexity of recursive DFS on a tree?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Linked List
next
Heap / Priority Queue
→
Progress is saved on this device