Tree Traversals
Compare depth-first traversal orders, level-order waves, Euler entry/exit times, and Morris's threaded O(1) walk.
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. Morris traversal removes the call stack entirely: it temporarily threads a right pointer from each node's inorder predecessor back to that node, follows the thread to climb back up, and removes it once used, visiting every node in inorder order with only O(1) auxiliary space.
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
thread predecessors for O(1) Morris
or use a queue for level orderComplexity — time O(n), space O(h) DFS · O(w) BFS · O(1) Morris.
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.
Return the root-left-right traversal of a binary tree.
Return tree values grouped from top level to bottom.
Encode a tree and restore the identical structure.