L13: Preorder, Inorder, and Postorder Traversals in One Traversal

1. Introduction and Problem Statement

When exploring Binary Trees, finding the three standard tree traversals—Preorder, Inorder, and Postorder—typically requires writing three separate recursive or iterative functions. Each standard traversal visits the nodes in a specific order:

• Preorder (Root, Left, Right): Process the root node first, then traverse the left subtree, followed by the right subtree.
• Inorder (Left, Root, Right): Traverse the left subtree first, process the root node, then traverse the right subtree.
• Postorder (Left, Right, Root): Traverse both subtrees first, and process the root node last.

While running three independent traversals takes $O(3N)$ time (which simplifies to $O(N)$), interviewers often challenge candidates to compute all three traversals simultaneously in a single traversal ($O(N)$ time) using an explicit stack and a state-tracking mechanism.

2. Core Mental Model and State Machine Analogy

To achieve all three traversals in one pass, we must remember where we are in the tree and how many times we have visited each node. Unlike standard stack-based iterative traversals that only store tree nodes, this approach stores a pair: (Node, State).

The Three States of a Node

Every node in the stack goes through three distinct states corresponding to when it interacts with the Preorder, Inorder, and Postorder lists:

3. Step-by-Step Algorithm Workflow

1. Initialize:
   • Create three separate lists/vectors: preorder, inorder, and postorder.
   • Create a stack that holds pairs of (TreeNode*, int state).
   • If the root is null, return empty lists. Otherwise, push (root, 1) to the stack.
2. Iterate: While the stack is not empty:
   • Look at the top element of the stack (node, state) without popping it yet.
   • Check the integer state:
     • If state == 1:
       • Add node->val to the preorder list.
       • Increment the state of this stack element to 2.
       • If node->left != nullptr, push (node->left, 1) onto the stack.
     • If state == 2:
       • Add node->val to the inorder list.
       • Increment the state of this stack element to 3.
       • If node->right != nullptr, push (node->right, 1) onto the stack.
     • If state == 3:
       • Add node->val to the postorder list.
       • Pop the element from the stack entirely.

4. Complete Dry Run Walkthrough

Let's trace a simple binary tree to see how states transition on the stack:

        1
       / \
      2   5
     / \   \
    3   4   6

Execution Trace Table

5. C++ Implementation

Here is the clean, production-ready C++ implementation using std::stack and std::pair:

#include <iostream>
#include <vector>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<std::vector<int>> preInPostTraversal(TreeNode* root) {
        std::vector<int> preorder, inorder, postorder;
        if (root == nullptr) {
            return {};
        }

        // Stack stores a pair of {Node*, state}
        // State 1: Preorder
        // State 2: Inorder
        // State 3: Postorder
        std::stack<std::pair<TreeNode*, int>> st;
        st.push({root, 1});

        while (!st.empty()) {
            auto it = st.top();
            st.pop();

            // This is part 1: Preorder
            if (it.second == 1) {
                preorder.push_back(it.first->val);
                it.second++; // Move state to 2 (Inorder)
                st.push(it); // Push updated state back

                if (it.first->left != nullptr) {
                    st.push({it.first->left, 1});
                }
            }
            // This is part 2: Inorder
            else if (it.second == 2) {
                inorder.push_back(it.first->val);
                it.second++; // Move state to 3 (Postorder)
                st.push(it); // Push updated state back

                if (it.first->right != nullptr) {
                    st.push({it.first->right, 1});
                }
            }
            // This is part 3: Postorder
            else {
                postorder.push_back(it.first->val);
                // State 3 reached: Do not push back, let it pop permanently
            }
        }

        return {preorder, inorder, postorder};
    }
};

6. Java Implementation

For Java developers, since std::pair is not natively available in standard collections, we can create a custom helper class Tuple or store objects in an array/custom wrapper.

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

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

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

public class TreeTraversal {
    public static List<List<Integer>> getTreeTraversal(TreeNode root) {
        List<Integer> preorder = new ArrayList<>();
        List<Integer> inorder = new ArrayList<>();
        List<Integer> postorder = new ArrayList<>();

        if (root == null) {
            return new ArrayList<>();
        }

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

        while (!st.isEmpty()) {
            Pair it = st.pop();

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

                if (it.node.left != null) {
                    st.push(new Pair(it.node.left, 1));
                }
            }
            // Inorder
            else if (it.state == 2) {
                inorder.add(it.node.val);
                it.state++;
                st.push(it);

                if (it.node.right != null) {
                    st.push(new Pair(it.node.right, 1));
                }
            }
            // Postorder
            else {
                postorder.add(it.node.val);
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        result.add(preorder);
        result.add(inorder);
        result.add(postorder);
        return result;
    }
}

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(3N) \approx \mathcal{O}(N)$
  • Each node is pushed and popped from the stack exactly three times (once for each state: 1, 2, and 3).
  • Thus, visiting all nodes across all traversals scales linearly with the total number of nodes $N$.
• Space Complexity: $\mathcal{O}(4N) \approx \mathcal{O}(N)$
  • Stack Space: In the worst-case scenario (a skewed tree like a linked list), the stack will hold $N$ elements at once, each storing a pointer and an integer state.
  • Result Storage: We store 3 separate lists, each holding $N$ integers, requiring $3N$ space. Combining stack and storage gives $\mathcal{O}(4N)$, which simplifies in Big-O notation to $\mathcal{O}(N)$.

8. Summary and Key Takeaways

• Unified Traversal: You can compute Preorder, Inorder, and Postorder traversals simultaneously in a single pass using an explicit stack.
• State Machine Pattern: Associate each stack entry with a state counter (1 for Preorder, 2 for Inorder, 3 for Postorder).
• Stack Re-insertion: Unlike traditional single-visit stack algorithms, when a node is at state 1 or 2, its state is incremented and it is pushed back onto the stack before pushing its child nodes.
• Postorder Finalization: When a node hits state 3, it is fully processed and popped for good, contributing its value to the postorder list.
• Optimal Efficiency: The approach achieves optimal $\mathcal{O}(N)$ time complexity, saving code duplication and demonstrating advanced stack manipulation skills during technical interviews.