Skip to content
Tutorials Center
My learning

Topics

Lesson 93 of 225 ยท Trees

Level-Order Traversal and Tree BFS

Master breadth-first search on binary trees in Python: level-order traversal with a queue, level lists, zigzag, right-side view, minimum depth and tree width.

Preorder, inorder and postorder dive deep before they go wide. Level-order traversal does the opposite: it visits the root, then all nodes one step away, then all nodes two steps away, and so on, like ripples spreading on a pond. On a tree this is breadth-first search (BFS), and its tool is a queue instead of a stack.

BFS is the right tool whenever a question is about levels or distance from the root: print the tree level by level, find the shallowest leaf, list the rightmost node of every level, or measure the widest level. The same pattern, with a visited set added, becomes graph BFS later in the course.

The idea

TEXT
        1          level 0:  1
       / \
      2   3        level 1:  2 3
     / \   \
    4   5   6      level 2:  4 5 6

level order: 1 2 3 4 5 6

A queue hands out items in the order they arrived (first in, first out), which is exactly the order we want:

  1. Put the root in the queue.
  2. Take the front node out and visit it.
  3. Add its left child and then its right child to the back.
  4. Repeat until the queue is empty.

Nodes of level k are always added before nodes of level k + 1, because level k + 1 nodes are only discovered while processing level k.

Python Basic level-order traversal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Use collections.deque, not a list with pop(0). Removing from the front of a list shifts every other element, which costs O(n) per removal and turns the whole traversal into O(n^2).

Grouping nodes by level

The flat list loses the level boundaries. The standard trick: at the start of each round, the queue holds exactly one level. Record len(queue) as the level size, then process that many nodes. Everything they add to the queue belongs to the next level.

TEXT
round 1: queue [1]        size 1 -> level [1]       queue becomes [2, 3]
round 2: queue [2, 3]     size 2 -> level [2, 3]    queue becomes [4, 5, 6]
round 3: queue [4, 5, 6]  size 3 -> level [4, 5, 6] queue becomes []

This for _ in range(len(queue)) loop is the template for almost every BFS tree problem. Memorize it.

Python Level-order as a list of levels

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(n) since every node enters and leaves the queue once. Space is O(w), where w is the maximum width of the tree: the queue never holds more than two adjacent levels, and the biggest single level dominates. For a perfect tree the last level has about n/2 nodes, so the space is O(n). For a skewed tree it is O(1).

DFS needs O(height) memory, BFS needs O(width) memory. On a very wide, shallow tree BFS is the memory hog; on a very tall, thin tree DFS is.

Zigzag level order

A classic variation: read the first level left to right, the second right to left, the third left to right again, and so on.

Brute force idea: compute levels(root) and then reverse every odd-indexed list. That is already O(n) and perfectly fine. It is also the clearest solution, so start there.

Slightly better: fill each level into a deque and use appendleft on right-to-left levels, so you never reverse afterward. Both approaches are O(n) time; the second avoids one extra pass.

Python Zigzag level order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The queue itself is always filled left to right; only the recording direction flips. Reversing the traversal order of the queue would break the next level's order.

Right-side view and left-side view

Imagine standing to the right of the tree. At each depth you see only the rightmost node. With the level template, that is simply the last node of every level.

Python Right-side view and leftmost values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The DFS version shows that BFS is not the only way. It remembers the depth in a parameter and records only the first node it reaches at each new depth. Both are O(n) time; the DFS one uses O(h) space instead of O(w).

Minimum depth: where BFS wins

The minimum depth is the number of nodes on the shortest path from the root to a leaf. DFS must explore the whole tree to be sure. BFS can stop at the first leaf it dequeues, because it reaches shallower nodes first. On a tree with a leaf near the top and a huge subtree elsewhere, that is a big saving.

Beware the trap: a node with one child is not a leaf. The minimum depth of the chain 1 -> 2 is 2, not 1.

Python Minimum depth with early exit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Width of a binary tree

The width of a level can mean "number of nodes", but a common harder version counts the gap between the leftmost and rightmost possible positions, including empty slots in between. Label the nodes like a heap array (root 0, children 2i+1 and 2i+2, or 1-based: 2i and 2i+1) and take last - first + 1 for each level.

To avoid the huge integers a very deep skewed tree would create, subtract the first index of the level before computing children (Python integers do not overflow, but the numbers get slow; in other languages they would overflow).

Python Maximum width including gaps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Problem Time Space
Level order / levels / side view O(n) O(w)
Zigzag O(n) O(w)
Minimum depth (BFS) O(n) worst, can stop early O(w)
Maximum width O(n) O(w)

Here n is the number of nodes and w is the maximum number of nodes on one level.

Common mistakes

  • queue.pop(0) on a list. Correct but O(n) per call. Use deque.popleft().
  • Reading len(queue) inside the loop instead of once before it. The queue grows while you process the level, so the loop would run into the next level.
  • Forgetting the empty-tree check and putting None into the queue, which crashes on node.val.
  • Treating a node with one child as a leaf in minimum-depth problems.
  • Reversing the queue for zigzag. Reverse only the recorded values.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which data structure drives level-order traversal?

    A queue releases nodes in the order they were discovered, so all nodes of one level come out before the next level.
  2. 2. What is the purpose of reading size = len(queue) before the inner loop?

    Children are appended while the level is processed, so the length must be captured first. Exactly size nodes belong to the current level.
  3. 3. A perfect binary tree has n nodes. What is the extra space of level-order traversal?

    The last level of a perfect tree holds about n/2 nodes, and the queue holds that whole level at its peak.
  4. 4. What is the minimum depth (counted in nodes) of the tree 1 with only a right child 2, where 2 is a leaf?

    Node 1 is not a leaf because it has a child. The only leaf is 2, so the shortest root-to-leaf path has 2 nodes.
  5. 5. Why can BFS stop early when looking for the minimum depth?

    All nodes at depth d are dequeued before any node at depth d + 1.

Summary

  • Level-order traversal is breadth-first search on a tree: a queue visits nodes in order of depth.
  • Use collections.deque; popleft() is O(1).
  • The level template, for _ in range(len(queue)), groups nodes by level and powers zigzag, side views, averages and width.
  • BFS uses O(width) memory, DFS uses O(height); BFS can stop early when searching for the shallowest match, as in minimum depth.
  • Side views also have a DFS solution that records the first node seen at each depth.
  • Always remember the empty tree, and that a node with one child is not a leaf.

Next: Binary Search Trees