🌲 Blog 2: Traversal Based (DFS) Pattern in Binary Trees

Traversal is the foundation of every tree problem. Once you master traversal, many problems reduce to small tweaks on top of it.

🔍 Identifying the Pattern

Whenever the problem talks about:

Visiting all nodes in a particular order (pre, in, post).
Building/recovering a tree from given traversal sequences.
Performing operations while visiting nodes. 👉 It’s a Traversal (DFS) problem.

🛠 Core Idea & Template

DFS traversals come in three main flavors:

Preorder (root → left → right)
Inorder (left → root → right)
Postorder (left → right → root)

👉 Recursive template:

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

    // Preorder step (before visiting children)
    dfs(root.left);

    // Inorder step (between left & right)
    dfs(root.right);

    // Postorder step (after visiting children)
}

👉 Iterative template (using stack):

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();
    // Process node here (Inorder)
    curr = curr.right;
}

✅ Classic Problems & Java Solutions

1. Binary Tree Inorder Traversal (LC 94)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = 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();
            res.add(curr.val); // Inorder position
            curr = curr.right;
        }
        return res;
    }
}

2. Binary Tree Preorder Traversal (LC 144)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

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

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val); // Preorder position

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return res;
    }
}

3. Binary Tree Postorder Traversal (LC 145)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if (root == null) return res;

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

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.addFirst(node.val); // Reverse of root-right-left
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return res;
    }
}

4. Construct Binary Tree from Preorder & Inorder (LC 105)

Classic DFS recursive construction.

class Solution {
    private Map<Integer, Integer> inorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int ps, int pe, int is, int ie) {
        if (ps > pe || is > ie) return null;

        TreeNode root = new TreeNode(preorder[ps]);
        int inRoot = inorderIndex.get(root.val);
        int leftSize = inRoot - is;

        root.left = build(preorder, ps + 1, ps + leftSize, is, inRoot - 1);
        root.right = build(preorder, ps + leftSize + 1, pe, inRoot + 1, ie);

        return root;
    }
}

5. Recover BST (LC 99)

Use inorder traversal to find misplaced nodes.

class Solution {
    TreeNode first = null, second = null, prev = new TreeNode(Integer.MIN_VALUE);

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;

        inorder(root.left);

        if (first == null && prev.val > root.val) {
            first = prev;
        }
        if (first != null && prev.val > root.val) {
            second = root;
        }
        prev = root;

        inorder(root.right);
    }
}

6. Flatten Binary Tree to Linked List (LC 114)

Do DFS postorder → rearrange pointers.

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.left);
        flatten(root.right);

        TreeNode rightSub = root.right;
        root.right = root.left;
        root.left = null;

        TreeNode curr = root;
        while (curr.right != null) curr = curr.right;
        curr.right = rightSub;
    }
}