Binary Tree · DFS

Visual EditorTree Problems

Pre, In & Post Order in One Traversal

Compute all three DFS traversals simultaneously in a single pass using an explicit stack and a visit-count per node.

StackDFSOptimizationInterview Hard

Key concepts at a glance — for those who already know the basics.

Problem Statement

Preorder, Inorder and Postorder in Single Traversal

Given the root of a binary tree, return preorder, inorder, and postorder traversals in one iterative traversal using a stack and node state.
Example

Input: root = [1, 2, 3, 4, 5, 6, 7]

Output: pre=[1,2,4,5,3,6,7], in=[4,2,5,1,6,3,7], post=[4,5,2,6,7,3,1]

Constraints

  • The number of nodes is in range [0, 10^5].
  • Node values may be negative and repeated; traversal order must remain deterministic.

01 · The core idea

Every node is visited exactly 3 times. The state counter decides what to do on each visit.

Normally, these need 3 separate DFS passes. This algorithm does all three in one pass.

02 · The three traversals compared

1

Preorder

[1, 2, 4, 5, 3, 6, 7]

2

Inorder

[4, 2, 5, 1, 6, 3, 7]

3

Postorder

[4, 5, 2, 6, 7, 3, 1]

03 · Algorithm steps

1

Push (root, state=1) onto the stack

Each stack frame is a (node, count) pair.

2

Pop top frame. Check the state counter.

Increment counter and push the frame back before doing any child push.

3

State 1 → add to pre[], push left child (state=1)

4

State 2 → add to in[], push right child (state=1)

5

State 3 → add to post[], do not push back

Node is fully processed. Naturally falls off the stack.

04 · Code

def allTraversals(root):
pre, ino, post = [], [], []
stack = [(root, 1)] // (node, state)
while stack:
node, state = stack.pop()
if state == 1: // first visit → preorder
pre.append(node.val)
stack.append((node, 2)) // come back at state 2
if node.left: stack.append((node.left, 1))
elif state == 2: // second visit → inorder
ino.append(node.val)
stack.append((node, 3)) // come back at state 3
if node.right: stack.append((node.right, 1))
else: // third visit → postorder
post.append(node.val)
return pre, ino, post

05 · Complexity

Time

O(n)

Each node is pushed/popped exactly 3 times. Total operations = 3n.

Space

O(n)

Stack holds at most O(h) frames at once. Output arrays together hold 3n values.

06 · Interview uses

Optimize multiple traversal calls

— when a problem requires more than one traversal result, this avoids repeated tree walks.

Iterative DFS mastery

— demonstrates deep understanding of the call stack and how recursion works under the hood.

Tree reconstruction

— preorder + inorder together uniquely identify a binary tree. Getting both in one pass is efficient.

Space-constrained environments

— avoids 3× recursion overhead when working with very deep or large trees.

Ready to see it in action?

Step through the visualizer to watch the algorithm state update live.

Open Visualizer