Preorder, Postorder, Inorder in a Single Traversal — Editorial

Opening the reading…

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

Create 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.

Return 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.

Push 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.

While 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.

For 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.

For 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.

For 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.

Return 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

MEASURE	BOUND	WHY
Time	O(n)	Each node's stack entry is processed exactly three times: once for each state. Every state performs constant work, and each child is pushed once, so no subtree is scanned again.
Space	O(n)	The output rows are excluded because they are required output. The stack has one entry for every active node; in a chain all n nodes can be active before the deepest node finishes, which is the worst shape and gives O(n) extra space.

Here n is the number of nodes in the tree. The three returned traversal rows are required output and are excluded from auxiliary space.

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

CPPThe stack state advances a node from preorder to inorder to postorder.

#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.

CPPThe recursive alternative places the three appends around the two subtree calls.

#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);
    }
};