🔥 One Loop Traversal (Preorder, Inorder, Postorder Together)

Idea

• Use a stack of (node, state).

• state tells us what stage the node is in:

  • 1 → preorder (before going left).
  • 2 → inorder (after left, before right).
  • 3 → postorder (after right).

Code (Java)

class Solution {
    static class Pair {
        TreeNode node;
        int state;
        Pair(TreeNode node, int state) {
            this.node = node;
            this.state = state;
        }
    }

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

        List<Integer> preorder = new ArrayList<>();
        List<Integer> inorder = new ArrayList<>();
        List<Integer> postorder = new ArrayList<>();

        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root, 1));

        while (!stack.isEmpty()) {
            Pair top = stack.pop();

            if (top.state == 1) {
                // Preorder
                preorder.add(top.node.val);
                top.state++;
                stack.push(top);

                if (top.node.left != null)
                    stack.push(new Pair(top.node.left, 1));

            } else if (top.state == 2) {
                // Inorder
                inorder.add(top.node.val);
                top.state++;
                stack.push(top);

                if (top.node.right != null)
                    stack.push(new Pair(top.node.right, 1));

            } else {
                // Postorder
                postorder.add(top.node.val);
            }
        }

        System.out.println("Preorder: " + preorder);
        System.out.println("Inorder: " + inorder);
        System.out.println("Postorder: " + postorder);
    }
}

---

✅ Example

Input tree:

      1
     / \
    2   3
   / \
  4   5

Output:

Preorder: [1, 2, 4, 5, 3]
Inorder: [4, 2, 5, 1, 3]
Postorder: [4, 5, 2, 3, 1]

---

⚡ Why This is Useful?

• You don’t write three separate traversals.
• Time complexity: O(n) (still visits each node once).
• Space: O(h) for stack (same as recursion depth).
• Easy to extend if interview asks for all traversals in one pass.

---