Preorder, Postorder, Inorder in a Single Traversal

Intuitionone node, three moments, three outputs

A node belongs in all three traversals, but not at the same time. Preorder records it before its left subtree, inorder records it after the left subtree and before the right subtree, and postorder records it after both subtrees. The iterative solution only needs to remember which of these three moments is next for each node.

Put the root on a stack with state 1. State 1 means the node has just been encountered, so record preorder and move into its left child. When that left side is finished, the node reaches state 2: record inorder and move into its right child. After the right side is finished, state 3 records postorder and removes the node. A missing child simply means the next state is processed immediately.

Approach

1. 1Create three result rows in the required order: preorder, inorder, and postorder. Keeping the rows separate lets each visit moment append directly to its destination instead of requiring a later rearrangement.
2. 2Return the three empty rows immediately when root is null, because there is no stack entry to process and the required result still has exactly three rows.
3. 3Push root with state 1. The state must travel with the node; storing only the node loses whether its left subtree, right subtree, or both have already been handled.
4. 4While the stack is not empty, inspect its top entry without removing it. The top is the active node whose next visit moment is ready, while lower entries must wait for its subtree to finish.
5. 5For state 1, change the state to 2, append the node value to preorder, and push the left child with state 1 when it exists. Changing the state before descending prevents the parent from recording preorder again after the child returns.
6. 6For state 2, change the state to 3, append the node value to inorder, and push the right child with state 1 when it exists. This places inorder precisely between the completed left subtree and the pending right subtree.
7. 7For state 3, append the node value to postorder and pop the entry. Both subtrees are now complete, so leaving the node on the stack would only repeat work and could prevent termination.
8. 8Return the three rows after the stack empties. Every node has then passed through all three states, so each traversal is complete without a second tree walk.

Complexityeach node advances through three constant-time states

Annotated solutionC++ · iterative · one stack entry per active node

#include <stack>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> allTraversals(TreeNode* root) {
        vector<vector<int>> answer(3);
        if (root == nullptr) {
            return answer;
        }

        stack<pair<TreeNode*, int>> st;
        st.push({root, 1});

        while (!st.empty()) {
            TreeNode* node = st.top().first;
            int state = st.top().second;

            if (state == 1) {
                st.top().second = 2;
                answer[0].push_back(node->val);
                if (node->left != nullptr) {
                    st.push({node->left, 1});
                }
            } else if (state == 2) {
                st.top().second = 3;
                answer[1].push_back(node->val);
                if (node->right != nullptr) {
                    st.push({node->right, 1});
                }
            } else {
                answer[2].push_back(node->val);
                st.pop();
            }
        }

        return answer;
    }
};

The two state assignments are the safety mechanism of the loop. Before descending to a child, the parent is advanced so that returning to it selects the next visit moment. The child starts at state 1 and therefore follows the exact same rule. This is the iterative equivalent of pausing a recursive call between its left and right subcalls, then finishing it after the right subcall.

The recursive alternativethe same three moments expressed by the call stack

Recursion provides the same ordering with less explicit bookkeeping: append preorder before the left call, inorder between the two calls, and postorder after the right call. It is not an asymptotic optimisation; the runtime call stack replaces the explicit stack and still uses O(n) space in a completely one-sided tree. The iterative form is safer when a tree can be as deep as 100000 nodes.

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> allTraversals(TreeNode* root) {
        vector<vector<int>> answer(3);
        walk(root, answer);
        return answer;
    }

private:
    void walk(TreeNode* node, vector<vector<int>>& answer) {
        if (node == nullptr) {
            return;
        }

        answer[0].push_back(node->val);
        walk(node->left, answer);
        answer[1].push_back(node->val);
        walk(node->right, answer);
        answer[2].push_back(node->val);
    }
};

Common mistakesthe state transitions must match the tree positions