Types of DFS (Tree Traversals)
Master Preorder, Inorder, and Postorder traversals: the building blocks of most Tree algorithms.
The Three Flavors of DFS
When traversing a Tree using Depth-First Search, the "depth-first" logic remains the same (go down before going sideways). However, the order in which we "process" (visit/print) the current node relative to its children defines the three main types:
- Preorder: Root → Left → Right
- Inorder: Left → Root → Right
- Postorder: Left → Right → Root
Problem: Standardize the Visit
Given a binary tree, return a list of values depending on the traversal order.
- Input: Tree
[1, null, 2, 3](1 is root, 2 is right child, 3 is left child of 2) - Preorder Output:
[1, 2, 3] - Inorder Output:
[1, 3, 2] - Postorder Output:
[3, 2, 1]
When to use each type?
Pattern Recognition:
- Preorder: Creating a copy of the tree, Prefix expression evaluation, Serialization.
- Inorder: Binary Search Tree (BST) validation (gives sorted order), Infix expression.
- Postorder: Deleting a tree (delete children before parent), Postfix evaluation, Computing height/size (need child info first).
Intuition: The Tour Route
Imagine tracing the outline of the tree starting from the left of the root.
- Preorder: Snap a photo the moment you arrive at a node for the first time.
- Inorder: Snap a photo only after you've returned from the left child but before going right.
- Postorder: Snap a photo only when you are leaving the node for the last time (finished both children).
Visualizing the Stack
Initializing...
The visualization represents a standard Preorder DFS. Notice how we process the parent immediately before diving into the children.
Iterative Approaches (Stack)
Using the call stack (recursion) is elegant, but sometimes we need to simulate it manually using an explicit stack.
- Preorder: Push Root. While stack: Pop, process, push Right, push Left.
- Inorder: Push all left nodes. Pop, process, move Right, repeat.
- Postorder: Tricky (Use 2 stacks or reverse Preorder Root-Right-Left).
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.