Preorder Traversal
Visits the root first, then recursively traverses left and right subtrees.
Visits all nodes level by level from top to bottom using a queue (BFS).
Level Order traversal, also called Breadth-First traversal, visits all nodes at depth d before any nodes at depth d+1. It processes the tree level by level, from top to bottom and left to right within each level. Unlike the three depth-first traversals (preorder, inorder, postorder), level order uses a queue rather than a stack, making it the tree-specific application of Breadth-First Search (BFS). BFS was first described by Konrad Zuse in 1945 in his rejected Ph.D. thesis and later independently reinvented by Edward F. Moore in 1959 for finding shortest paths in mazes.
For a tree with root 1, left child 2 (with children 4 and 5), and right child 3 (with children 6 and 7), level order visits: 1, 2, 3, 4, 5, 6, 7. Level 0 (just the root) is visited first, then level 1 (both children of the root), then level 2 (all grandchildren), and so on.
A common enhancement is to track level boundaries. Before processing each level, record the current queue size. Then dequeue exactly that many nodes, which gives you all nodes at the current depth. This technique is essential for problems that need per-level information, such as computing the average value at each level or collecting a list of lists grouped by depth.
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(w) where w = max width of tree |
Every node is enqueued and dequeued exactly once, giving O(n) time. The space is determined by the maximum number of nodes in the queue at any point, which equals the width of the widest level. For a complete binary tree, the last level holds roughly n/2 nodes, so the worst-case space is O(n). For a skewed tree (essentially a linked list), each level has at most one node, so the space is O(1).
The fundamental difference is the data structure used: depth-first traversals use a stack (explicitly or via recursion), while level order uses a queue. This leads to different exploration patterns. Depth-first traversals dive deep into one branch before backtracking, while level order explores the tree in concentric rings outward from the root. This distinction matters when the tree structure influences the problem: use depth-first when you need to explore full root-to-leaf paths, and use level order when you need to compare nodes at the same depth or find the shallowest node satisfying some condition.
Level order traversal is the natural choice for several important tree problems. Finding the minimum depth of a tree (the shallowest leaf) is most efficiently done with BFS, because you can stop as soon as you encounter the first leaf -- depth-first approaches might explore an entire deep branch before finding a shallow leaf. Tree serialization for array-based representations (where the tree is stored as a flat array with index arithmetic) uses level order because it maps directly to the array layout. Printing or visualizing a tree level by level requires level order traversal. Finding the rightmost or leftmost node at each level ("right side view" or "left side view" problems) is naturally solved with level order.
Level order traversal is heavily tested in technical interviews. Classic problems include zigzag (alternating direction) level order traversal, populating next-right pointers for each node, finding the maximum value in each level, and computing the width of the binary tree (the distance between the leftmost and rightmost non-null nodes at any level).
Choose level order traversal when you need to process nodes by depth, find the shallowest node matching a criterion, serialize a tree into an array layout, or solve any problem that requires comparing or grouping nodes at the same level. For problems that require root-to-leaf path analysis or bottom-up aggregation, depth-first traversals are usually more natural.