Tree Traversals
Tree traversal is the process of visiting every node in a tree exactly once in a specific order. For binary trees, four traversal strategies are standard. ...
The Four Core Traversal Orders
Tree traversal is the process of visiting every node in a tree exactly once in a specific order. For binary trees, four traversal strategies are standard. In pre-order traversal, you visit the current node first, then recursively traverse the left subtree, then the right subtree. In in-order traversal, you traverse the left subtree first, then visit the current node, then traverse the right subtree. In post-order traversal, you traverse both subtrees before visiting the current node. Level-order traversal visits nodes level by level from top to bottom, left to right within each level.
Each traversal order reveals different structural information. Pre-order produces a sequence that can reconstruct the tree if the structure is also known. In-order on a binary search tree produces keys in sorted ascending order — a critical property. Post-order is natural for deletion and for evaluating expression trees because children are processed before their parent. Level-order is often used to find the shortest path in an unweighted tree.
All four traversals visit every node exactly once, so they all run in O(N) time. Recursive implementations use O(H) call stack space where H is the tree height. Iterative implementations use an explicit stack or queue.
Iterative Implementations Using a Stack
Recursive traversals are elegant but risk stack overflow on deep trees. Converting them to iterative form uses an explicit stack. For iterative pre-order: push the root; while the stack is not empty, pop a node, visit it, push its right child then its left child (right first so left is processed first). For iterative in-order: use a pointer starting at root; push nodes going left until null, then pop, visit, and move right.
Post-order is trickier iteratively. One approach uses two stacks: push root to stack one; while stack one is not empty, pop to stack two, push left then right child to stack one; finally pop and visit all nodes in stack two. This reverses the reversed pre-order, giving post-order.
Level-order uses a queue. Enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its non-null children. This naturally processes nodes level by level. The space used is O(W) where W is the maximum width of the tree, which in a perfect binary tree equals approximately N divided by 2 at the last level.
Worked Example and Interview Insight
Worked example: given two arrays representing the pre-order and in-order traversals of a binary tree, reconstruct the tree. The first element of pre-order is always the root. Find that value in the in-order array — everything to its left is the left subtree and everything to its right is the right subtree. Apply this rule recursively to reconstruct both subtrees. Using a hash map to store in-order indices, the reconstruction runs in O(N) time and O(N) space.
Morris traversal is an advanced technique that achieves O(N) time and O(1) space for in-order traversal by temporarily threading null right pointers to the in-order successor, then restoring them. It is rarely required in interviews but impresses interviewers when mentioned.
Interview tip: when given any tree problem, immediately state which traversal order you intend to use and why. Interviewers specifically assess whether you can identify that post-order is needed when a parent's computation depends on both children, or that level-order is needed to process the tree breadth-first for shortest-path or level-grouping tasks.