Level Order Traversal, step by step.

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

What is level order traversal?

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.

Is level order traversal the same as BFS?

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.

How does level order traversal work? A queue, level by level

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.

Level order traversal algorithm: pseudocode

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.

Level order traversal example: the queue step by step

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.

Level order traversal with a queue

All steps as text
  1. Explore how the breadth-first traversal works.
  2. Start at the root (7) of the binary tree and enqueue it into the queue.
  3. Then dequeue the root (7) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  4. Enqueue the left child (24) into the queue.
  5. Enqueue the right child (62) into the queue. After that, the next node needs to be dequeued from the queue.
  6. Dequeue the node (24) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  7. Enqueue the left child (92) into the queue.
  8. Enqueue the right child (11) into the queue. After that, the next node needs to be dequeued from the queue.
  9. Dequeue the node (62) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  10. Enqueue the left child (76) into the queue.
  11. Enqueue the right child (13) into the queue. After that, the next node needs to be dequeued from the queue.
  12. Dequeue the node (92) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  13. Enqueue the left child (1) into the queue.
  14. Enqueue the right child (9) into the queue. After that, the next node needs to be dequeued from the queue.
  15. Dequeue the node (11) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  16. Enqueue the left child (84) into the queue.
  17. Enqueue the right child (53) into the queue. After that, the next node needs to be dequeued from the queue.
  18. Dequeue the node (76) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  19. Enqueue the left child (72) into the queue.
  20. Enqueue the right child (33) into the queue. After that, the next node needs to be dequeued from the queue.
  21. Dequeue the node (13) and visit it. If it has a left child, the left child needs to be enqueued into the queue. The right child, if it exists, also needs to be enqueued.
  22. Enqueue the left child (32) into the queue.
  23. Enqueue the right child (83) into the queue. After that, the next node needs to be dequeued from the queue.
  24. Dequeue the node (1) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  25. Dequeue the node (9) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  26. Dequeue the node (84) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  27. Dequeue the node (53) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  28. Dequeue the node (72) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  29. Dequeue the node (33) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  30. Dequeue the node (32) and visit it. Since this node has no children, the next node needs to be dequeued from the queue.
  31. Dequeue the node (83) and visit it. Since the queue is now empty, all nodes have been visited and the traversal is complete.
  32. Level order visited the 15 nodes in the order 7, 24, 62, 92, 11, 76, 13, 1, 9, 84, 53, 72, 33, 32, 83: level by level from the root, each level from left to right.
Level order traversal with a queue. Last step: Level order visited the 15 nodes in the order 7, 24, 62, 92, 11, 76, 13, 1, 9, 84, 53, 72, 33, 32, 83: level by level from the root, each level from left to right.

Level order traversal and the array representation of a tree

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.

Why does level order traversal use a queue?

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.

Printing level order traversal line by line

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.

Level order traversal using recursion or a stack: why a queue

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.

Level order traversal time and space complexity

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.

Level order traversal in Python, Java and C++

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++.

Level order vs preorder, inorder and postorder: BFS vs DFS on a tree

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.

Applications of level order traversal

  • Printing a hierarchy: an organization chart or a folder tree, one level per line.
  • Nearest first: a search for a node near the root ends sooner, and the first leaf dequeued gives the tree's minimum depth.
  • Serializing a tree: the keys in level order, with a marker for each missing child; the same queue rebuilds the tree.
  • Complete trees and heaps: a tree is complete when, in level order, no node follows the first missing child, and a heap keeps its nodes in that order.

The default tree here.
Your own tree 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.

A tree you build

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.

Three depth-first orders

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.

Level order and its uses

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.

Python, Java and C++

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.

Quiz

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.

The same queue on graphs

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.

Level by level,
left to right.

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