Level-Order Traversal with deque
24 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Level-order traversal visits a tree row by row with a queue. This lesson builds it with collections.deque, splits the rows apart and uses them for the right-side view, zigzag order and the shortest path to a leaf.
Row by row with a queue
Level-order traversal visits a tree row by row, from the root down and from left to right. It uses a queue, so the nodes found first are handled first. It is also called breadth-first search.
Depth-first orders go deep before they go wide. To visit row by row, keep a queue of nodes waiting. Take the first one, record it and add its children at the back.
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def level_order(root): result, queue = [], deque([root]) while queue: node = queue.popleft() if node: result.append(node.val) queue.extend((node.left, node.right)) return resultprint(level_order(root))Example 1 · Watch the queue
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))queue = deque([root])while queue: node = queue.popleft() print("take", node.val, "queue:", [n.val for n in queue]) for child in (node.left, node.right): if child: queue.append(child)take 1 queue: [] take 2 queue: [3] take 3 queue: [4, 5] take 4 queue: [5, 6] take 5 queue: [6] take 6 queue: []
What this code does
- Each node is taken from the front, and its children go to the back.
- Node 3 is taken before node 4, so the row 2, 3 is finished before the row 4, 5, 6 begins.
Children join the back of the line, so the whole row of the parents is finished before any child is taken. Time is O(n). The queue can hold a full row, so space is O(w), where w is the widest row.
One list for each level
Many problems need the rows kept apart. At the start of each round the queue holds exactly one row. Record that row, then replace the queue by the children of its nodes.
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def levels(root): result, queue = [], deque([root] if root else []) while queue: result.append([node.val for node in queue]) queue = deque(c for node in queue for c in (node.left, node.right) if c) return resultprint(levels(root))Example 2 · The classic row-by-row loop
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def levels(root): result, queue = [], deque([root] if root else []) while queue: level = [] for _ in range(len(queue)): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result
print(levels(root))[[1], [2, 3], [4, 5, 6]]
What this code does
len(queue)is read once, at the start of the round, so the loop handles exactly one row.- Children added during the round wait for the next one. Many interviewers expect this version.
The comprehension builds the next row from the current one and skips missing children. The result is [[1], [2, 3], [4, 5, 6]]. The classic way to split rows is to loop len(queue) times, shown in the examples.
Why a deque and not a list
Queue is a first in, first out line: items leave in the order they arrived. In Python, collections.deque adds and removes items at either end in O(1) time, so it is the usual choice.
A queue gives out items in the order they came in. A list is slow for that: pop(0) moves every other item one place. A deque removes from the left end in constant time.
from collections import dequequeue = deque(["Asha", "Ben", "Chen"])queue.append("Dina")print(queue.popleft(), queue.popleft())print(queue)items = ["Asha", "Ben", "Chen"]print(items.pop(0), items)Example 3 · First come, first served
from collections import deque
tickets = deque()for customer in ["Asha", "Ben", "Chen"]: tickets.append(customer)while tickets: print("serving", tickets.popleft())serving Asha serving Ben serving Chen
What this code does
- The customer who arrived first leaves first. A stack would do the opposite.
- A traversal uses the same idea: the first node found is the first one handled.
Both give the same answer. pop(0) on a list costs O(n) each time, so a traversal of n nodes could cost O(n squared). deque.popleft() costs O(1).
Right-side view and other row questions
Once rows are separate, many questions are one line. The right-side view is the last value of each row. The widest row is the longest list. A row's total is its sum.
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def levels(root): result, queue = [], deque([root] if root else []) while queue: result.append([node.val for node in queue]) queue = deque(c for node in queue for c in (node.left, node.right) if c) return resultrows = levels(root)print([row[-1] for row in rows])print(max(len(row) for row in rows), [sum(row) for row in rows])Example 4 · Several views of the same rows
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, TreeNode(4)))def levels(root): result, queue = [], deque([root] if root else []) while queue: result.append([node.val for node in queue]) queue = deque(c for node in queue for c in (node.left, node.right) if c) return result
rows = levels(root)print("rows", rows)print("right view", [row[-1] for row in rows])print("left view", [row[0] for row in rows])print("row totals", [sum(row) for row in rows])rows [[1], [2, 3], [5, 4]] right view [1, 3, 4] left view [1, 2, 5] row totals [1, 5, 9]
What this code does
- This tree has 5 under 2 and 4 under 3, so the left view and right view differ.
- Rows are plain lists, so any list tool works on them.
Example 5 · Zigzag order
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
def levels(root): result, queue = [], deque([root] if root else []) while queue: result.append([node.val for node in queue]) queue = deque(c for node in queue for c in (node.left, node.right) if c) return result
zigzag = [row[::-1] if i % 2 else row for i, row in enumerate(levels(root))]print(zigzag)[[1], [3, 2], [4, 5, 6]]
What this code does
- Odd rows are reversed with a slice.
enumerategives the row number. - The queue itself is not changed. Only the finished rows are reordered.
Someone standing on the right side sees the last node of every row, which is 1, 3 and 6 here.
Depth-first can build rows too
A recursive call that knows its depth can put each value in its row, with no queue. The first value to reach a new depth starts a new list.
class TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, rightroot = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))def fill(node, depth, rows): if node: if depth == len(rows): rows.append([]) rows[depth].append(node.val) fill(node.left, depth + 1, rows) fill(node.right, depth + 1, rows)rows = []fill(root, 0, rows)print(rows)Example 6 · Stop at the first leaf
from collections import dequeclass TreeNode: def __init__(self, val, left=None, right=None): self.val, self.left, self.right = val, left, right
def min_depth(root): queue, depth = deque([root]), 0 while queue: depth += 1 for _ in range(len(queue)): node = queue.popleft() if node.left is None and node.right is None: return depth queue.extend(c for c in (node.left, node.right) if c) return 0
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))print(min_depth(root))2
What this code does
- Level order meets the shallowest leaf first, so it can stop at once. A depth-first search must look at every node.
- Depth is counted in nodes, so the root alone has depth 1.
Going left before right keeps each row in left-to-right order. Choose the queue when the first match at the shallowest level matters, as in the shortest path. Choose recursion when a row is only needed at the end.
Next step
Check your understanding
12 quick questions