All patterns
Tree Traversals
Trees
Intermediate
Interactive
Compare depth-first traversal orders, level-order waves, and Euler entry/exit times.
Time
O(n)
Space
O(h) DFS · O(w) BFS
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
Tree traversal changes meaning based on when a node is recorded. Preorder visits before both subtrees, inorder between them, postorder after both, and Euler Tour records entry and exit. Level order replaces recursion with a FIFO queue to process one depth at a time.
Analogy
A reusable way to think about organizing and navigating structured data efficiently.
When to reach for it
- The relationships between values drive the algorithm.
- You need efficient traversal, lookup, or updates.
- An interview problem names or implies this structure.
Language-independent template
choose traversal order
visit before, between, or after children
or use a queue for level orderComplexity — time O(n), space O(h) DFS · O(w) BFS.
Common mistakes
- Losing a pointer before saving its next target.
- Breaking the structure invariant during an update.
- Forgetting empty and single-node cases.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Return the root-left-right traversal of a binary tree.
Medium
Return tree values grouped from top level to bottom.
Hard
Encode a tree and restore the identical structure.
Variations
Traversal
Insertion and deletion
Search and reconstruction