Trees (DFS/BFS)
Traverses tree structures either by going deep first (DFS) or level by level (BFS).
The Approach
- For DFS: Use recursion or an explicit stack. Go as deep as possible down one path before backtracking.
- For BFS: Use a queue. Visit all nodes at the current level before moving to the next level.
- Keep track of visited nodes if the structure can contain cycles (though less common in basic tree problems).
Types of Trees (DFS/BFS)
Depth-First Search (DFS)
Includes Pre-order, In-order, and Post-order traversals.
DFS Traversal
1
2
3
4
5
Order:
Breadth-First Search (BFS)
Also known as Level-Order Traversal.
DFS Traversal
1
2
3
4
5
Order:
Common Problems
Maximum Depth of Binary Tree
Trees (DFS/BFS)
Binary Tree Level Order Traversal
Trees (BFS)
Same Tree
Trees (DFS/BFS)
Path Sum
Trees (DFS)
Diameter of Binary Tree
Trees (DFS)