Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

DFS Traversals
DSA

DFS Traversals

Learn recursive and iterative depth-first traversals of binary trees.

DFS Traversal visits every node in a tree by exploring depth first — going as deep as possible before backtracking.

Its core advantage:

Traversal order determines the sequence of node processing — each order suits different problems.

Focus on recognizing:

“Traverse tree” + “Recursive” + “Left/right” = DFS Traversal

Pattern Table

PatternTypical QuestionsTrigger
PreorderCopy tree, serializeRoot → Left → Right
InorderBST sorted orderLeft → Root → Right
PostorderDelete tree, subtree DPLeft → Right → Root

Mental Trigger

Position of root processing: Pre = before children, In = between, Post = after.

1. Generic Java DFS Template (Base)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public void dfs(TreeNode root) {
    if (root == null) return;

    // preorder: process root here
    dfs(root.left);
    // inorder: process root here
    dfs(root.right);
    // postorder: process root here
}
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def dfs(root):
    if root is None:
        return

    # preorder: process root here
    dfs(root.left)
    # inorder: process root here
    dfs(root.right)
    # postorder: process root here
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void dfs(TreeNode* root) {
    if (root == nullptr) return;

    // preorder: process root here
    dfs(root->left);
    // inorder: process root here
    dfs(root->right);
    // postorder: process root here
}
class TreeNode {
  constructor(x) {
    this.val = x;
    this.left = null;
    this.right = null;
  }
}

function dfs(root) {
  if (root === null) return;

  // preorder: process root here
  dfs(root.left);
  // inorder: process root here
  dfs(root.right);
  // postorder: process root here
}

Everything else in DFS Traversal is just a modification of this template.

Pattern 1: Recursive Traversals

One tree, three orders — the visit line’s position names the traversal. Press ▶ to animate.

Tree Traversals — In / Pre / Post Order

See how the single line that 'visits' a node changes the output for inorder, preorder, and postorder.

Recurse left then right in every order; only the placement of the visit/print line differs — inorder (L,root,R) yields sorted keys, preorder (root,L,R) is good for copying, postorder (L,R,root) for bottom-up work.

TREE VISUALIZER
Steps –
21435
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        inorder:  L, root, R
                      
                        2
                        preorder: root, L, R
                      
                        3
                        postorder: L, R, root

Java Code

public void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

public void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}

public void postorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}
def preorder(root, result):
    if root is None:
        return
    result.append(root.val)
    preorder(root.left, result)
    preorder(root.right, result)

def inorder(root, result):
    if root is None:
        return
    inorder(root.left, result)
    result.append(root.val)
    inorder(root.right, result)

def postorder(root, result):
    if root is None:
        return
    postorder(root.left, result)
    postorder(root.right, result)
    result.append(root.val)
void preorder(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    result.push_back(root->val);
    preorder(root->left, result);
    preorder(root->right, result);
}

void inorder(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorder(root->left, result);
    result.push_back(root->val);
    inorder(root->right, result);
}

void postorder(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->val);
}
function preorder(root, result) {
  if (root === null) return;
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
}

function inorder(root, result) {
  if (root === null) return;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
}

function postorder(root, result) {
  if (root === null) return;
  postorder(root.left, result);
  postorder(root.right, result);
  result.push(root.val);
}

Preorder = root first. Inorder = root between children. Postorder = root last.

Pattern 2: Iterative Inorder (Stack)

Grind left spines onto a stack, pop, hop right. Press ▶ to animate.

Iterative Inorder Traversal

Inorder (L, root, R) using an explicit stack — the basis of BST iteration.

Grind down the left spine pushing nodes, then pop-visit and step right. The recursive call stack becomes an explicit stack, making the walk pausable (e.g., for kth-smallest).

TREE VISUALIZER
Steps –
21435
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        while stack or cur:
                      
                        2
                          while cur: push(cur); cur = left
                      
                        3
                          cur = pop() → visit
                      
                        4
                          cur = cur.right

Java Code

public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }

    return result;
}
def inorder_iterative(root):
    result = []
    stack = []
    curr = root

    while curr is not None or stack:
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right

    return result
vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr != nullptr || !st.empty()) {
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }

    return result;
}
function inorderIterative(root) {
  const result = [];
  const stack = [];
  let curr = root;

  while (curr !== null || stack.length > 0) {
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }

  return result;
}

What Changed from the Base Template?

Explicit stack replaces call stack

Base:

// recursion handles the stack implicitly

Changed:

Stack<TreeNode> stack = new Stack<>();

because iterative traversal uses an explicit stack to simulate the call stack.

Push all left descendants first

Added:

while (curr != null) {
    stack.push(curr);
    curr = curr.left;
}

to go as far left as possible before processing — matching the inorder(root.left) recursive call.

Iterative Inorder = Explicit stack + Push all left + Process on pop + Go right.

Pattern 3: Iterative Preorder (Stack)

Pop-visit-push(right,left) — LIFO puts left back on top. Press ▶ to animate.

Iterative Preorder Traversal

Preorder (root, L, R) using an explicit stack.

Push the root; repeatedly pop-visit, then push the right child before the left so the left pops first under LIFO. Produces root-first order ideal for serialization.

TREE VISUALIZER
Steps –
21435
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        stack = [root]
                      
                        2
                        while stack:
                      
                        3
                          n = pop → visit
                      
                        4
                          push right, then left

Java Code

public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        result.add(curr.val);

        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }

    return result;
}
def preorder_iterative(root):
    result = []
    if root is None:
        return result

    stack = [root]

    while stack:
        curr = stack.pop()
        result.append(curr.val)

        if curr.right is not None:
            stack.append(curr.right)
        if curr.left is not None:
            stack.append(curr.left)

    return result
vector<int> preorderIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;

    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* curr = st.top();
        st.pop();
        result.push_back(curr->val);

        if (curr->right != nullptr) st.push(curr->right);
        if (curr->left != nullptr) st.push(curr->left);
    }

    return result;
}
function preorderIterative(root) {
  const result = [];
  if (root === null) return result;

  const stack = [root];

  while (stack.length > 0) {
    const curr = stack.pop();
    result.push(curr.val);

    if (curr.right !== null) stack.push(curr.right);
    if (curr.left !== null) stack.push(curr.left);
  }

  return result;
}

What Changed from the Base Template?

Process root before children

Base (inorder):

// process on pop, after left subtree

Changed:

result.add(curr.val); // process immediately on pop

because preorder processes root before exploring left and right.

Push right before left

Added:

if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);

because stack is LIFO — pushing right first ensures left is processed first.

Iterative Preorder = Stack + Push root + Process on pop + Push right then left.

DFS Pattern Evolution

Recursive DFS (base template)
    ↓
Iterative Inorder
    (+ explicit stack + go-left-till-null)
    ↓
Iterative Preorder
    (+ process on pop + push right before left)

Common Mistakes

Forgetting base case if (root == null) return.

This is the most common cause of stack overflow in recursion.

Wrong push order in iterative preorder.

Push right before left to maintain left-first order with LIFO stack.

Infinite loop in iterative inorder.

Always advance curr = curr.right after popping — otherwise you loop on the same node.

Recognition Cheat Sheet

If you see…Think…
Traverse entire treeDFS or BFS
BST sorted orderInorder DFS
Copy/serialize treePreorder DFS
Delete tree / subtree DPPostorder DFS
Avoid recursion depth limitIterative stack

My Private Notes

Notes are auto-saved locally to this device.