aloalgoTree Traversals (DFS & BFS)
Tree traversal is the process of visiting every node in a tree exactly once. There are two main approaches: Depth-First Search (DFS) which goes deep before wide, and Breadth-First Search (BFS) which goes wide before deep.DFS Traversal Orders
DFS has three variations based on when you process the current node relative to its children:| Order | Pattern | Use Case |
|---|---|---|
| Preorder | Node → Left → Right | Copy tree, prefix expressions |
| Inorder | Left → Node → Right | BST gives sorted order |
| Postorder | Left → Right → Node | Delete tree, postfix expressions |
Preorder Traversal
Process the node first, then recurse on left and right children.Inorder Traversal
Recurse on left, process the node, then recurse on right. For BSTs, this gives nodes in sorted order.Postorder Traversal
Recurse on both children first, then process the node. Useful when you need information from children before processing the parent.BFS / Level Order Traversal
Visit all nodes at depth d before visiting nodes at depth d+1. Uses a queue to process nodes level by level.DFS vs BFS
| Aspect | DFS | BFS |
|---|---|---|
| Data structure | Stack (or recursion) | Queue |
| Space complexity | O(h) height of tree | O(w) width of tree |
| Best for | Deep trees, path problems | Wide trees, shortest path |
| Finds shortest path? | No | Yes (unweighted) |
When to Use DFS vs BFS
Use DFS when:- You need to explore all paths (path sum, root-to-leaf)
- You need information from children before processing parent
- The answer is likely deep in the tree
- You're doing tree transformations or modifications
- You need level-by-level processing
- You're finding minimum depth or shortest path
- You need to process nodes closest to root first
- The answer is likely near the top of the tree
Common Interview Tips
- Know all three DFS orders: Be able to write preorder, inorder, and postorder from memory.
- Inorder for BST: If the tree is a BST, inorder gives you sorted values.
- BFS for level-based problems: Minimum depth, level averages, right-side view.
- Iterative vs recursive: Know both - iterative avoids stack overflow for deep trees.
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.