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
Pick an order and run it. The walk is the same in all three — the outlined calls go down and come back up along the same path — and only the step where a node is appended moves. Each node shows the order it was appended in; switch orders on the same tree and watch the numbers change.
Dry Run Comparison
Tree: Root(1) -> Left(2), Right(3).
| Step | Preorder (Root-L-R) | Inorder (L-Root-R) | Postorder (L-R-Root) |
|---|---|---|---|
| 1 | Visit 1. Go Left(2). | Go Left(2). | Go Left(2). |
| 2 | Visit 2. Go Left(null). | Go Left(null). Visit 2. | Go Left(null). Go Right(null). |
| 3 | Back to 2. Go Right(null). | Back to 2. Go Right. | Back to 2. Visit 2. Return. |
| 4 | Back to 1. Go Right(3). | Visit 1. Go Right(3). | Back to 1. Go Right(3). |
| 5 | Visit 3. Children null. | Left null. Visit 3. | Left null. Right null. Visit 3. |
| 6 | Done. | Done. | Back to 1. Visit 1. Done. |
The Code Templates
The three methods are identical except for one line: where result gets the node — before both calls, between them, or after both.
Types of DFS (Tree Traversals) Code
1function preorder(node, result) {2 if (!node) return;3 result.push(node.val);4 preorder(node.left, result);5 preorder(node.right, result);6}78function inorder(node, result) {9 if (!node) return;10 inorder(node.left, result);11 result.push(node.val);12 inorder(node.right, result);13}1415function postorder(node, result) {16 if (!node) return;17 postorder(node.left, result);18 postorder(node.right, result);19 result.push(node.val);20}
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).
Edge Cases & Checks
Standard tree checks apply:
Empty Tree: Root is null. Return empty list.
Single Node: Left/Right are null. Recursion handles this (base case).
Skewed Tree: Effectively a Linked List. Recursion depth might hit limits (O(N)).
Summary
Recap:
- Preorder: Root first.
- Inorder: Root middle (Sorted for BST).
- Postorder: Root last (Bottom-up processing).