What does it solve?
Depth-first traversal walks as deep as possible before backtracking. The three classic orders visit the same nodes but record them at different moments:
Preorder = node, then left, then right (root first). Inorder = left, node, right (sorted order for a BST). Postorder = left, right, then node (children before parent, used for deletion & bottom-up sums). All are O(N), visiting each node once.
The core idea
Complexity
Time complexity
O(N)
Every node is visited exactly once regardless of order. The recursion tree mirrors the actual tree.
Space complexity
O(H)
The call stack (or explicit stack) is as deep as the tree height H, up to O(N) for a skewed tree.
Examples & edge cases
Live animation — preorder
on the call stack
active node
recorded (output)
Binary tree (small purple number = output position)
Call stack (recursion depth)
empty
Traversal output
none yet
Current step detail
at = —
depth = —
action = —
output = —
Step — of —
active node
—
current
stack depth
—
recursion
action
—
enter/record/return
recorded
—
of total
Select an example and press Play to start.
✓ Done
SpeedMedium
Step-by-step table
| Step | action | node | depth | stack | output |
|---|
C++ implementation
preorder.cpp
My Notes
📝Notes✅
Practice this problem