All Three Traversals
Description
Given the root of a binary tree, compute all three classical depth-first traversals — Preorder, Inorder, and Postorder — and return them as three separate lists.
- Preorder visits: Node → Left → Right
- Inorder visits: Left → Node → Right
- Postorder visits: Left → Right → Node
Your task is to produce these three traversals. Ideally you should aim to collect all three in a single pass over the tree rather than running three independent traversals.
Examples
Example 1
Input:
1
/ \
2 3
Output:
- Preorder: [1, 2, 3]
- Inorder: [2, 1, 3]
- Postorder: [2, 3, 1]
Explanation: In preorder we visit the root 1 first, then left child 2, then right child 3. In inorder we visit the left child 2 first, then root 1, then right child 3. In postorder we visit left child 2, then right child 3, and finally the root 1.
Example 2
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output:
- Preorder: [1, 2, 4, 5, 3, 6, 7]
- Inorder: [4, 2, 5, 1, 6, 3, 7]
- Postorder: [4, 5, 2, 6, 7, 3, 1]
Explanation: This is a complete binary tree with three levels. Preorder visits root first then recursively each subtree's root before its children. Inorder visits the leftmost leaf first and works upward. Postorder visits all children before parents, ending at the root.
Example 3
Input:
1
\
2
/
3
Output:
- Preorder: [1, 2, 3]
- Inorder: [1, 3, 2]
- Postorder: [3, 2, 1]
Explanation: Node 1 has no left child, only a right child 2 which itself has a left child 3. This skewed structure shows that traversal order matters even when subtrees are missing.
Constraints
- 1 ≤ Number of nodes ≤ 10^5
- -10^9 ≤ Node.val ≤ 10^9
Editorial
Brute Force
Intuition
The most straightforward way to get all three traversals is to simply run each traversal independently using recursion. Recursion naturally models the tree structure: for preorder you process the current node first, then recurse on left and right; for inorder you recurse left, process the node, then recurse right; and for postorder you recurse both children before processing the node.
Think of it like reading a book in three different orders — first reading every chapter title before the content (preorder), then reading content left-to-right as written (inorder), and finally reading summaries after finishing each chapter (postorder). You walk through the entire book three separate times.
Step-by-Step Explanation
Let's trace through the tree:
1
/ \
2 3
Preorder Traversal (Node → Left → Right):
Step 1: Visit root node 1 → add 1 to preorder. Recurse left.
Step 2: Visit node 2 → add 2 to preorder. No children. Backtrack.
Step 3: Visit node 3 → add 3 to preorder. No children. Done.
Preorder result: [1, 2, 3]
Inorder Traversal (Left → Node → Right):
Step 4: Recurse to leftmost — node 2 has no left child. Visit node 2 → add 2 to inorder.
Step 5: Back at root 1 → add 1 to inorder.
Step 6: Visit node 3 → add 3 to inorder.
Inorder result: [2, 1, 3]
Postorder Traversal (Left → Right → Node):
Step 7: Recurse to node 2 — no children → add 2 to postorder.
Step 8: Visit node 3 — no children → add 3 to postorder.
Step 9: All children of root done → add 1 to postorder.
Postorder result: [2, 3, 1]
We traversed the tree three separate times to get all three results.
Three Separate Recursive Traversals — Watch how we traverse the same tree three times — once for each traversal order — visiting nodes in different sequences each time.
Algorithm
- Define a recursive function
preorder(node): if node is null return; append node value; recurse left; recurse right. - Define a recursive function
inorder(node): if node is null return; recurse left; append node value; recurse right. - Define a recursive function
postorder(node): if node is null return; recurse left; recurse right; append node value. - Call all three functions on the root and return the three result lists.
Code
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
void preHelper(Node* node, vector<int>& res) {
if (!node) return;
res.push_back(node->data);
preHelper(node->left, res);
preHelper(node->right, res);
}
void inHelper(Node* node, vector<int>& res) {
if (!node) return;
inHelper(node->left, res);
res.push_back(node->data);
inHelper(node->right, res);
}
void postHelper(Node* node, vector<int>& res) {
if (!node) return;
postHelper(node->left, res);
postHelper(node->right, res);
res.push_back(node->data);
}
vector<vector<int>> allTraversals(Node* root) {
vector<int> pre, in, post;
preHelper(root, pre);
inHelper(root, in);
postHelper(root, post);
return {pre, in, post};
}
};class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def allTraversals(self, root):
pre, ino, post = [], [], []
def preorder(node):
if not node:
return
pre.append(node.data)
preorder(node.left)
preorder(node.right)
def inorder(node):
if not node:
return
inorder(node.left)
ino.append(node.data)
inorder(node.right)
def postorder(node):
if not node:
return
postorder(node.left)
postorder(node.right)
post.append(node.data)
preorder(root)
inorder(root)
postorder(root)
return [pre, ino, post]import java.util.*;
class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
class Solution {
void preHelper(Node node, List<Integer> res) {
if (node == null) return;
res.add(node.data);
preHelper(node.left, res);
preHelper(node.right, res);
}
void inHelper(Node node, List<Integer> res) {
if (node == null) return;
inHelper(node.left, res);
res.add(node.data);
inHelper(node.right, res);
}
void postHelper(Node node, List<Integer> res) {
if (node == null) return;
postHelper(node.left, res);
postHelper(node.right, res);
res.add(node.data);
}
List<List<Integer>> allTraversals(Node root) {
List<Integer> pre = new ArrayList<>();
List<Integer> in = new ArrayList<>();
List<Integer> post = new ArrayList<>();
preHelper(root, pre);
inHelper(root, in);
postHelper(root, post);
return Arrays.asList(pre, in, post);
}
}Complexity Analysis
Time Complexity: O(3n) = O(n)
We traverse the entire tree three times — once for preorder, once for inorder, and once for postorder. Each traversal visits every node exactly once, so the total work is 3 × n = O(n). However, the constant factor of 3 is not ideal.
Space Complexity: O(h) for the call stack
Each recursive traversal uses stack space proportional to the height h of the tree. In the worst case (skewed tree), h = n, so space is O(n). For a balanced tree, h = log n. The three output lists together hold 3n elements but that is output space, not auxiliary.
Why This Approach Is Not Efficient
While the brute force approach has O(n) time complexity per traversal, it traverses the tree three separate times. Each traversal visits every node once, so the total number of node visits is 3n. For large trees with up to 10^5 nodes, this means 3 × 10^5 node accesses.
More importantly, from a systems perspective, three separate recursive traversals mean three separate call stacks being built and torn down. Each traversal independently follows the entire tree structure, which is redundant — the information about which node to visit next (parent-child relationships) is the same in all three traversals.
The key insight is: during a single traversal, every node is naturally encountered at three distinct moments — when we first arrive (preorder position), when we return from the left subtree (inorder position), and when we return from the right subtree (postorder position). If we could track which stage each node is at, we could collect all three results in a single pass.
Optimal Approach - Single Stack with Status Codes
Intuition
The elegant solution uses a single stack where each entry is a pair: (node, status). The status tracks which phase of processing the node is in:
- Status 1: The node has just been pushed — this is the preorder moment (we see the node for the first time). After recording it in preorder, we change its status to 2 and push its left child.
- Status 2: We have returned from the left subtree — this is the inorder moment. After recording it in inorder, we change its status to 3 and push its right child.
- Status 3: We have returned from both subtrees — this is the postorder moment. We record it in postorder and pop it off the stack.
Imagine a delivery person visiting houses on a street. Each house has three tasks: drop off a morning paper (preorder), collect noon mail (inorder), and pick up evening packages (postorder). Instead of making three trips down the street, the delivery person visits each house once but comes back to it as the route naturally loops — handling one task each time they pass by. The status code is like a checklist at each house tracking which tasks are already done.
Step-by-Step Explanation
Let's trace through the tree:
1
/ \
2 3
/ \ / \
4 5 6 7
Step 1: Push (1, status=1) onto the stack. Stack: [(1,1)].
Step 2: Top is (1,1). Status 1 → add 1 to preorder. Change status to 2. Push left child (2,1). Stack: [(1,2), (2,1)]. Preorder: [1].
Step 3: Top is (2,1). Status 1 → add 2 to preorder. Change status to 2. Push left child (4,1). Stack: [(1,2), (2,2), (4,1)]. Preorder: [1, 2].
Step 4: Top is (4,1). Status 1 → add 4 to preorder. Change status to 2. Node 4 has no left child, so nothing pushed. Stack: [(1,2), (2,2), (4,2)]. Preorder: [1, 2, 4].
Step 5: Top is (4,2). Status 2 → add 4 to inorder. Change status to 3. Node 4 has no right child. Stack: [(1,2), (2,2), (4,3)]. Inorder: [4].
Step 6: Top is (4,3). Status 3 → add 4 to postorder. Pop (4,3). Stack: [(1,2), (2,2)]. Postorder: [4].
Step 7: Top is (2,2). Status 2 → add 2 to inorder. Change status to 3. Push right child (5,1). Stack: [(1,2), (2,3), (5,1)]. Inorder: [4, 2].
Step 8: Top is (5,1). Status 1 → add 5 to preorder. Change status to 2. No left child. Stack: [(1,2), (2,3), (5,2)]. Preorder: [1, 2, 4, 5].
Step 9: Top is (5,2). Status 2 → add 5 to inorder. Change status to 3. No right child. Stack: [(1,2), (2,3), (5,3)]. Inorder: [4, 2, 5].
Step 10: Top is (5,3). Status 3 → add 5 to postorder. Pop. Stack: [(1,2), (2,3)]. Postorder: [4, 5].
Step 11: Top is (2,3). Status 3 → add 2 to postorder. Pop. Stack: [(1,2)]. Postorder: [4, 5, 2].
Step 12: Top is (1,2). Status 2 → add 1 to inorder. Change status to 3. Push right child (3,1). Stack: [(1,3), (3,1)]. Inorder: [4, 2, 5, 1].
Step 13: Top is (3,1). Status 1 → add 3 to preorder. Change status to 2. Push left child (6,1). Stack: [(1,3), (3,2), (6,1)]. Preorder: [1, 2, 4, 5, 3].
Step 14: Top is (6,1). Status 1 → add 6 to preorder. Change status to 2. No left child. Stack: [(1,3), (3,2), (6,2)]. Preorder: [1, 2, 4, 5, 3, 6].
Step 15: Top is (6,2). Status 2 → add 6 to inorder. Change status to 3. No right child. Stack: [(1,3), (3,2), (6,3)]. Inorder: [4, 2, 5, 1, 6].
Step 16: Top is (6,3). Status 3 → add 6 to postorder. Pop. Stack: [(1,3), (3,2)]. Postorder: [4, 5, 2, 6].
Step 17: Top is (3,2). Status 2 → add 3 to inorder. Change status to 3. Push right child (7,1). Stack: [(1,3), (3,3), (7,1)]. Inorder: [4, 2, 5, 1, 6, 3].
Step 18: Top is (7,1). Status 1 → add 7 to preorder. Change status to 2. No left child. Stack: [(1,3), (3,3), (7,2)]. Preorder: [1, 2, 4, 5, 3, 6, 7].
Step 19: Top is (7,2). Status 2 → add 7 to inorder. Change status to 3. No right child. Stack: [(1,3), (3,3), (7,3)]. Inorder: [4, 2, 5, 1, 6, 3, 7].
Step 20: Top is (7,3). Status 3 → add 7 to postorder. Pop. Stack: [(1,3), (3,3)]. Postorder: [4, 5, 2, 6, 7].
Step 21: Top is (3,3). Status 3 → add 3 to postorder. Pop. Stack: [(1,3)]. Postorder: [4, 5, 2, 6, 7, 3].
Step 22: Top is (1,3). Status 3 → add 1 to postorder. Pop. Stack empty. Postorder: [4, 5, 2, 6, 7, 3, 1].
Final Results:
- Preorder: [1, 2, 4, 5, 3, 6, 7]
- Inorder: [4, 2, 5, 1, 6, 3, 7]
- Postorder: [4, 5, 2, 6, 7, 3, 1]
Single Stack with Status Codes — All Three Traversals in One Pass — Watch how each node enters the stack once and has its status updated from 1→2→3, getting added to preorder, inorder, and postorder at the appropriate moment.
Algorithm
- Initialize three empty lists: preorder, inorder, postorder.
- Initialize a stack and push (root, status=1).
- While the stack is not empty:
a. Peek at the top element (node, status).
b. If status == 1:- Add node's value to preorder.
- Change status to 2.
- If node has a left child, push (left_child, 1) onto the stack.
c. If status == 2: - Add node's value to inorder.
- Change status to 3.
- If node has a right child, push (right_child, 1) onto the stack.
d. If status == 3: - Add node's value to postorder.
- Pop the element from the stack.
- Return all three lists.
Code
#include <vector>
#include <stack>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<vector<int>> allTraversal(Node* root) {
vector<int> pre, in, post;
if (!root) return {pre, in, post};
// Stack stores pairs of (node pointer, status)
// status 1 = preorder moment
// status 2 = inorder moment
// status 3 = postorder moment
stack<pair<Node*, int>> st;
st.push({root, 1});
while (!st.empty()) {
auto& [node, status] = st.top();
if (status == 1) {
// Preorder: visit node before its subtrees
pre.push_back(node->data);
status = 2;
if (node->left) {
st.push({node->left, 1});
}
} else if (status == 2) {
// Inorder: visit node between left and right subtrees
in.push_back(node->data);
status = 3;
if (node->right) {
st.push({node->right, 1});
}
} else {
// Postorder: visit node after both subtrees
post.push_back(node->data);
st.pop();
}
}
return {pre, in, post};
}
};class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
class Solution:
def allTraversal(self, root):
pre, ino, post = [], [], []
if not root:
return [pre, ino, post]
# Stack stores [node, status]
# status 1 = preorder moment
# status 2 = inorder moment
# status 3 = postorder moment
stack = [[root, 1]]
while stack:
entry = stack[-1]
node, status = entry[0], entry[1]
if status == 1:
# Preorder: record node before subtrees
pre.append(node.data)
entry[1] = 2
if node.left:
stack.append([node.left, 1])
elif status == 2:
# Inorder: record node between subtrees
ino.append(node.data)
entry[1] = 3
if node.right:
stack.append([node.right, 1])
else:
# Postorder: record node after both subtrees
post.append(node.data)
stack.pop()
return [pre, ino, post]import java.util.*;
class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
class Solution {
public List<List<Integer>> allTraversal(Node root) {
List<Integer> pre = new ArrayList<>();
List<Integer> in = new ArrayList<>();
List<Integer> post = new ArrayList<>();
if (root == null) {
return Arrays.asList(pre, in, post);
}
// Stack stores: [0] = node, [1] = status (as Integer)
// Using a Deque of Object arrays for mutability
Deque<Object[]> stack = new ArrayDeque<>();
stack.push(new Object[]{root, 1});
while (!stack.isEmpty()) {
Object[] top = stack.peek();
Node node = (Node) top[0];
int status = (int) top[1];
if (status == 1) {
// Preorder moment
pre.add(node.data);
top[1] = 2;
if (node.left != null) {
stack.push(new Object[]{node.left, 1});
}
} else if (status == 2) {
// Inorder moment
in.add(node.data);
top[1] = 3;
if (node.right != null) {
stack.push(new Object[]{node.right, 1});
}
} else {
// Postorder moment
post.add(node.data);
stack.pop();
}
}
return Arrays.asList(pre, in, post);
}
}Complexity Analysis
Time Complexity: O(n)
Each node is pushed onto the stack exactly once and has its status updated exactly three times (1→2→3). Each status update does O(1) work (appending to a list and possibly pushing a child). So the total work across all nodes is 3n operations, which is O(n). Unlike the brute force, we traverse the tree structure only once instead of three times.
Space Complexity: O(h)
The stack holds at most one path from root to a leaf at any time, which is the height h of the tree. In the worst case (completely skewed tree), h = n, giving O(n) space. For a balanced tree, h = log n. The three output lists hold 3n total elements but that is required output space, not additional auxiliary space.