On this page

Preorder, Inorder & Postorder in One Traversal

Given the root of a binary tree, return its preorder, inorder and postorder traversals all in a single traversal, without running three separate passes.

Intuition

Every example below uses this tree:

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

In the recursive versions, every node is actually touched three times: once on the way down (before going left), once after returning from the left subtree, and once after returning from the right subtree. Preorder records on the first touch, inorder on the second, and postorder on the third.

So if we remember how many times each node has been touched, one walk can feed all three answers.

Approach: Stack of (Node, State)

Push (root, 1) onto a stack. While the stack is not empty, look at the top pair (node, state):

  • State 1 (first visit, going down): add the value to preorder, set the state to 2, and if a left child exists, push (left, 1).
  • State 2 (back from the left): add the value to inorder, set the state to 3, and if a right child exists, push (right, 1).
  • State 3 (back from the right): add the value to postorder and pop the node.

The state is just a counter saying which of the three visits this is. For the sample tree this produces:

  • Preorder: 1, 2, 4, 5, 3, 6
  • Inorder: 4, 2, 5, 1, 3, 6
  • Postorder: 4, 5, 2, 6, 3, 1

Code

vector<vector<int>> allTraversals(TreeNode* root) {
vector<int> pre, in, post;
if (root == nullptr) return {pre, in, post};
stack<pair<TreeNode*, int>> st;
st.push({root, 1});
while (!st.empty()) {
auto& top = st.top();
TreeNode* node = top.first;
if (top.second == 1) {
pre.push_back(node->val);
top.second = 2;
if (node->left != nullptr) st.push({node->left, 1});
} else if (top.second == 2) {
in.push_back(node->val);
top.second = 3;
if (node->right != nullptr) st.push({node->right, 1});
} else {
post.push_back(node->val);
st.pop();
}
}
return {pre, in, post};
}

Complexity

Time: O(3n) = O(n)

Each node is touched exactly three times, once per state, so the total work is a constant multiple of n.

Space: O(h) stack, O(n) output

The stack holds one root-to-node path, so O(h). The three result lists together hold 3n values.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"In a recursive traversal each node is touched three times: going down, coming back from the left, and coming back from the right. Preorder records on the first touch, inorder on the second, and postorder on the third. So I keep a stack of node and state pairs, starting with the root in state 1. In state 1 I add to preorder, move to state 2 and push the left child. In state 2 I add to inorder, move to state 3 and push the right child. In state 3 I add to postorder and pop. One pass gives all three lists. Time is O of n, about three touches per node, and the stack space is O of h."
Next TopicMaximum Depth of Binary Tree