AlgoVerse

Level-order traversal

Visit the tree's nodes level by level, top to bottom and left to right, with a queue; BFS on a tree.

The preorder, inorder and postorder traversals are depth-first: they go to the bottom of a branch first. A level-order traversal visits every node at depth 0, then depth 1, then depth 2, and so on.

Read the full explanation ↓
Input:
n=7PDF export

The same tree as the depth-first traversals; the output 15, 6, 18, 3, 7, 17, 20 goes level by level.

  1. from collections import deque
  4. class Node:
  5. def __init__(self, key):
  6. self.key = key
  7. self.left = None
  8. self.right = None
  11. def level_order(root):
  12. out = []
  13. if root is None:
  14. return out
  15. queue = deque([root])
  16. while queue:
  17. node = queue.popleft()
  18. out.append(node.key)
  19. if node.left is not None:
  20. queue.append(node.left)
  21. if node.right is not None:
  22. queue.append(node.right)
  23. return out

Invariant: The queue always holds the rest of the current level followed by the start of the next level, left to right.

Start

36715171820

Local variables

Orange = changed in this step

root object

  • key = 15
  • left = Node(key=6, left=Node(key=3, left=None, right=None), right=Node(key=7, left=None, right=None))
  • right = Node(key=18, left=Node(key=17, left=None, right=None), right=Node(key=20, left=None, right=None))

Call stack

  1. level_order()line 11
Step 1 of 47
Black = visit · Orange = key stepstart: 0/1 · visit: 0/7 · enqueue: 0/6

    How the work grows with input size

    Average of 8 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • visit
    • current input (n=7)
    0510153579111315n = number of keysvisit
    Show as a table
    nvisit
    33
    55
    77
    99
    1111
    1313
    1515
    Explanation

    The idea

    The preorder, inorder and postorder traversals are depth-first: they go to the bottom of a branch first. A level-order traversal visits every node at depth 0, then depth 1, then depth 2, and so on.

    The algorithm

    Use a queue (first in, first out):

    1. Put the root in the queue.
    2. While the queue is not empty: take the first node, visit it, and add its left and right children to the back.

    This is BFS on a graph; since a tree has no cycles, nodes need no "seen" mark.

    Cost

    Each node enters and leaves the queue once: O(n). The queue grows at most to the size of the widest level.

    What to watch in the trace

    • Visited nodes are filled in; the queue is in the memory panel.