Pre + Post + Inorder in One Traversal
Produce preorder, inorder and postorder lists in a single traversal.
Open on GeeksforGeeks ↗02
Intuition
Each node is visited exactly three times during a DFS: on arrival (pre), between children (in), after children (post). Push (node, state) on a stack; each pop records the node in one list, bumps its state, and schedules the next child.
03
Approach
1
State 1, 2, 3
State 1: record preorder, push left. State 2: record inorder, push right. State 3: record postorder, done.
2
Re-push with incremented state
Pop (node, s); if s < 3 re-push (node, s+1) before pushing the child — the node re-surfaces after that child's subtree completes.
3
One pass, three answers
Every node cycles through the three states exactly once → O(n) total.
04
Solution & live demo
python
▶1def all_traversals(root):
▶2 pre, ino, post = [], [], []
▶3 if not root: return pre, ino, post
▶4 stack = [(root, 1)]
▶5 while stack:
▶6 node, state = stack.pop()
▶7 if state == 1:
▶8 pre.append(node.val)
▶9 stack.append((node, 2))
▶10 if node.left: stack.append((node.left, 1))
▶11 elif state == 2:
▶12 ino.append(node.val)
▶13 stack.append((node, 3))
▶14 if node.right: stack.append((node.right, 1))
▶15 else:
▶16 post.append(node.val)
▶17 return pre, ino, post
05
Edge cases
Skewed tree
Stack depth reaches n — same as recursion would.
Empty tree
All three lists empty.
06
Complexity
Time
O(n)
Space
O(h)
Three visits per node, one stack.