Tree Traversals (BFS/DFS)
Master inorder, preorder, postorder, and level-order to unlock all tree problems
Recognition Signals
Problem asks to visit nodes in a specific order
Need level-by-level processing (BFS) or depth-first exploration (DFS)
Phrases like 'zigzag level order', 'right side view', 'boundary traversal'
Need to collect nodes at specific depths or in specific sequences
Pro Tips
BFS uses a Queue; DFS uses recursion or an explicit Stack
For zigzag, alternate the direction of insertion at each level
Iterative inorder using a stack is the foundation for BST iterator design
Approach
BFS: Use a queue, process level by level. DFS: Use recursion or stack. Inorder (left-root-right) gives sorted order for BST. Preorder (root-left-right) for tree serialization. Postorder (left-right-root) for deletion and evaluation.
Code Template
| 1 | // Level Order Traversal (BFS) |
| 2 | public List<List<Integer>> levelOrder(TreeNode root) { |
| 3 | List<List<Integer>> result = new ArrayList<>(); |
| 4 | if (root == null) return result; |
| 5 | Queue<TreeNode> queue = new LinkedList<>(); |
| 6 | queue.offer(root); |
| 7 | while (!queue.isEmpty()) { |
| 8 | int levelSize = queue.size(); |
| 9 | List<Integer> currentLevel = new ArrayList<>(); |
| 10 | for (int i = 0; i < levelSize; i++) { |
| 11 | TreeNode node = queue.poll(); |
| 12 | currentLevel.add(node.val); |
| 13 | if (node.left != null) queue.offer(node.left); |
| 14 | if (node.right != null) queue.offer(node.right); |
| 15 | } |
| 16 | result.add(currentLevel); |
| 17 | } |
| 18 | return result; |
| 19 | } |