Level order traversal, also called breadth-first traversal, visits the nodes of a binary tree level by level from the root down, each level from left to right. A queue holds the nodes still to visit, and the walk takes O(n) time for n nodes. This page explains how it works, with a step-by-step animation of level order traversal on a 15-node binary tree from the VisiGrab app.
// how level order traversal works
Level order traversal visits every node of a binary tree once, level by level: the root, then its children, then their children, each level from left to right. A node's level is the number of links between it and the root, so the root is on level 0. It is also called breadth-first traversal, the VisiGrab app's name for it. A queue holds the nodes waiting their turn, and the walk takes O(n) time for a tree of n nodes.
Yes: level order traversal is breadth-first search (BFS) run on a tree from its root, so it is breadth-first, not depth-first. Two parts of graph BFS drop out. A tree has no cycles and each node but the root has one parent, so every node is reached once, by the link from its parent, and needs no visited mark. And the neighbors to enqueue are just the node's children, read from its left and right links, with no adjacency matrix or list.
A queue is first in, first out: enqueue adds a node at the rear, and dequeue removes the node at the front, the one that has waited longest.
1. Enqueue the root: the queue starts with the root alone.
2. Dequeue and visit: remove the front node and visit it, for example by printing its key.
3. Enqueue its children: add its left child at the rear, then its right child. A missing child is skipped, so a leaf adds nothing.
Steps 2 and 3 repeat until the queue is empty. The levels cannot mix: the nodes of a level all join the queue while the level above is visited, before any node of the level below, so they also leave first. The parents leave from left to right, each adding its left child first, so each level joins from left to right too.
The app's code is one function, breadthFirstTraverse or breadth_first_traversal, and each node's visit prints its key. In pseudocode:
breadthFirstTraverse(root)
if root is none
return
queue = empty queue
queue.enqueue(root)
while queue is not empty
node = queue.dequeue()
node.visit()
if node.left is not none
queue.enqueue(node.left)
if node.right is not none
queue.enqueue(node.right)
node.left and node.right are the links to the children, none where a child is missing. The first test handles an empty tree; the app's code instead wraps the rest in a test that the root is not null. Each node passes through enqueue, dequeue and visit once, so the while loop runs n times.
The player below runs the app's breadth-first traversal on its default tree, 15 nodes on four levels, with the queue on the right. It visits 7, 24, 62, 92, 11, 76, 13, 1, 9, 84, 53, 72, 33, 32, 83. The dotted line joins each visit to the next, along a level and then back to the left end of the level below, so apart from 7 → 24 it follows no edge.
That visit order is the array the app builds the tree from. The app keeps a tree as 15 slots in level order: the children of the node at index i sit at 2i + 1 and 2i + 2, as in a min-heap, and an empty slot means no node. Level order reads such an array from left to right, skipping the empty slots. LeetCode writes its tree inputs in level order too, with null for a missing child, but it leaves out the slots under a missing node, so 2i + 1 and 2i + 2 do not apply to its lists.
A queue hands out nodes in the order they joined it, first in, first out. All the nodes of a level join while the level above is visited, so they leave together, left to right, before any node of the next level. A stack would hand back the newest node and run down one branch instead: with the right child pushed first, the same loop visits in preorder.
To get one list per level, as LeetCode 102 asks, or print one level per line, read the queue's size when a level starts: the queue then holds exactly that level. Dequeue that many nodes, enqueue their children, then close the list or end the line.
A stack hands back the newest node, the child just added, so the walk runs down one branch: the same loop with a stack, pushing the right child before the left, visits in preorder, as the app's iterative preorder does. Recursion runs on the call stack, so it is depth-first too. It can still collect the levels: a preorder walk that passes each node's level down and appends the node to that level's list fills every list from left to right in O(n) time. Printing one level per pass, each pass starting from the root, takes O(n2) on a chain-shaped tree.
The time is O(n): one pass of the loop per node. The queue holds parts of at most two adjacent levels, so the extra space is O(w), where w is the number of nodes on the widest level. A perfect tree has (n + 1) / 2 leaves, so there the space is O(n): on the player's tree the eight leaves fill all eight slots of the queue. A recursive depth-first walk keeps one path on the call stack, O(h) for a tree of height h. The app's iterative preorder and inorder also stay within O(h) and never hold more than four nodes of the player's tree, while its two-stack postorder puts all 15 nodes on the second stack before the first visit. On a chain-shaped tree, where w is 1 and h is n − 1, the two bounds swap.
The app shows the function in all three languages.
Note
The app's Python code dequeues with queue.pop(0), as its graph BFS does. On a perfect tree the whole last level, about half the nodes, waits in the queue at once, so there the dequeues alone cost O(n2); collections.deque and popleft() take O(1) each.
The full source code is on GitHub, in Python, Java and C++.
Preorder, inorder and postorder are depth-first: each finishes a subtree before it starts the next, so preorder reaches the leaf 1, on level 3, before 62, on level 1. All four visit every node once in O(n) time.
// in the app
In VisiGrab, breadth-first traversal is one of four traversals of the same 15-node tree, each in its own color, with a message for every enqueue and dequeue.
Custom opens a template of 15 node slots on four levels: give any white node a key from 0 to 99, or delete a node with its whole subtree. The traversal then starts over on your tree, and Restart keeps it.
Preorder, inorder and postorder traversal walk the same default tree, each in its own color: preorder and inorder with one stack, postorder with two, where every node moves to the second stack before the first visit.
The info dialog gives level order as another name for the walk, sets it against the depth-first orders, and names two uses: printing a hierarchy level by level and searching for a node likely to sit near the root.
One iterative function per language, on a list, an ArrayDeque and a std::queue, after a note on why the walk does not suit recursion, with a link to the full source on GitHub.
Five questions with an explanation for every option: where the waiting nodes are kept, what follows a visit, which child joins first, which tasks suit the walk, and how it differs from the depth-first orders.
Breadth-First Search runs this queue on example graphs, where cycles call for visited marks, and the Graph Constructor runs BFS on a graph you draw. The Queue topic shows enqueue and dequeue on a circular array and on a linked list.
// build your own
Download VisiGrab to watch the queue walk the default tree, then build a tree of your own and see where each node falls in the order.
Level order traversal is one of 30+ topics. See them all