GeeksforGeeks Easy

Pre + Post + Inorder in One Traversal

Produce preorder, inorder and postorder lists in a single traversal.

treestacktraversal

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.

How to spot this pattern

One stack carrying (node, state) pairs simulates the three points a recursive call passes through each node: before the left call, between the calls, and after the right call. Emitting at state 1, 2, 3 gives preorder, inorder, and postorder from a single pass — this is literally what the call stack does, made explicit.

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

▶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

Common pitfalls

Not re-pushing the node with its next state

✗ Wrong

if state == 1:
    pre.append(node.val)
    if node.left: stack.append((node.left, 1))

✓ Right

if state == 1:
    pre.append(node.val)
    stack.append((node, 2))
    if node.left: stack.append((node.left, 1))

The node must be revisited twice more, once after the left subtree and once after the right. Dropping the re-push means inorder and postorder never receive it.

Pushing the child before the node's next state

✗ Wrong

stack.append((node.left, 1))
stack.append((node, 2))

✓ Right

stack.append((node, 2))
if node.left: stack.append((node.left, 1))

A stack pops in reverse, so the child must be pushed last to be processed first. Reversing the order visits the node's state-2 step before its left subtree, scrambling the inorder output.

Running three separate traversals

✗ Wrong

return preorder(root), inorder(root), postorder(root)

✓ Right

stack = [(root, 1)]

Three passes is three times the tree walking, and the point of the exercise is seeing that all three orders are the same walk sampled at different moments. One pass makes that relationship visible.

06

Edge cases

Skewed tree

Stack depth reaches n — same as recursion would.

Empty tree

All three lists empty.

07

Complexity

Time

O(n)

Space

O(h)

Three visits per node, one stack.