🌿

DFS Tree Traversal — Pre / In / Post-order

One recursive pattern, three visit timings. Change when you call result.add(node.val) — before, between, or after the recursive calls — to get pre-, in-, or post-order traversal.

🌿 Pre-order: Root First 🔶 In-order: BST Sorted 🟣 Post-order: Root Last Time O(n) Space O(h)

📋 When to Use

Pre-order — serialize tree, clone, construct from traversal, prefix expression
In-order — produce sorted output from BST, validate BST, kth smallest
Post-order — compute height/diameter, delete tree, evaluate expression trees
All three: whenever you need to process every node exactly once
Bottom-up DFS return values — height, max path sum, diameter

💡 The only difference between the three is the placement of result.add(node.val): before both recursive calls (pre), between them (in), or after both (post).

⚡ Complexity

Time

O(n)

Space (stack)

O(h)

Where n = number of nodes, h = height of tree.
Best case (balanced): O(log n) stack space.
Worst case (skewed/linked list): O(n) stack space.
Every node is visited exactly once — O(n) time regardless of order.

Problem Given a binary tree with 7 nodes (root = 1, left = [2,4,5], right = [3,6,7]), traverse it in Pre-order, In-order, and Post-order. Same tree — three visit orderings, each used for a different purpose: serialize, sort (BST), and compute height/diameter.
Input: root = [1,2,3,4,5,6,7] · Answer: Pre [1,2,4,5,3,6,7] · In [4,2,5,1,6,3,7] · Post [4,5,2,6,7,3,1]

Step 0 / 8

🔍 Init 📌 Visit Node ⬇️ Descend ✅ Done

🌿 Pre-order: ROOT → Left → Right. Visit the current node before recursing into children. The root is always first, leaves appear in left-to-right order.

// dfs(node) — pre-order skeleton

🌲 Binary Tree

active

in stack

visited

default

📚 Call Stack

— empty —

📝 Result:

[ waiting... ]

📊 Traversal Comparison — Same Tree

🌿 Pre-order

        ① 1② 2③ 4④ 5⑤ 3⑥ 6⑦ 7
      

Root visited FIRST

🔶 In-order

① 4② 2③ 5④ 1⑤ 6⑥ 3⑦ 7

BST → sorted order

🟣 Post-order

① 4② 5③ 2④ 6⑤ 7⑥ 3⑦ 1

Root visited LAST

🧩 Pattern Skeleton Java 8

// ─── Pre-order (Root → Left → Right) ────────────────
void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);         // ① visit ROOT first
    preorder(node.left, result);  // ② then left subtree
    preorder(node.right, result); // ③ then right subtree
}

// ─── In-order (Left → Root → Right) ─────────────────
void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);   // ① recurse left first
    result.add(node.val);         // ② visit ROOT between
    inorder(node.right, result);  // ③ then right subtree
}

// ─── Post-order (Left → Right → Root) ───────────────
void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);  // ① recurse left first
    postorder(node.right, result); // ② then right subtree
    result.add(node.val);          // ③ visit ROOT last
}

// ─── Generic DFS (bottom-up, returns computed value) ─
int dfs(TreeNode node) {
    if (node == null) return 0;   // base case
    int left  = dfs(node.left);    // get left result
    int right = dfs(node.right);   // get right result
    // use left + right to compute answer
    ans = Math.max(ans, left + right); // e.g. diameter
    return 1 + Math.max(left, right);  // e.g. height
}

🎯 Practice Problems

#144 Binary Tree Preorder Traversal 🌿 pre-order Easy #94 Binary Tree Inorder Traversal 🔶 in-order Easy #145 Binary Tree Postorder Traversal 🟣 post-order Easy #104 Maximum Depth of Binary Tree 🟣 post-order DFS return Easy #543 Diameter of Binary Tree 🟣 post-order, ans=left+right Easy #226 Invert Binary Tree 🌿 pre-order Easy #236 Lowest Common Ancestor of a Binary Tree 🟣 post-order Medium #105 Construct Tree from Pre+Inorder 🌿🔶 pre + in-order Medium #297 Serialize and Deserialize Binary Tree 🌿 pre-order Hard