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 12 / \3 2 34 / \ \5 4 5 6In 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
Each node is touched exactly three times, once per state, so the total work is a constant multiple of n.
The stack holds one root-to-node path, so O(h). The three result lists together hold 3n values.