Going across instead of down

A queue instead of the call stack, and the one line that turns a flat walk into levels.

Key idea

When depth-first is the wrong tool

Recursion naturally goes deep before it goes wide. Some questions are about the tree level by level: what is on each row, what is the leftmost node of each row, how far down is the nearest leaf.

Those want breadth-first traversal, which visits everything at one depth before moving to the next. It uses an explicit queue rather than the call stack.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5from collections import deque6 7def visit_order(root):8    if root is None:9        return []10    order = []11    queue = deque([root])12    while queue:13        node = queue.popleft()14        order.append(node.val)15        if node.left:16            queue.append(node.left)17        if node.right:18            queue.append(node.right)19    return order20 21print(visit_order(T(1, T(2, T(4), T(5)), T(3))))

Why it works

Snapshot the queue length

At the top of each round, the queue holds exactly the nodes of the current level and nothing else. So record its length before processing, then process exactly that many nodes.

Everything added during those steps belongs to the next level, and it lands behind the ones you are still processing. The invariant is: at the start of each round, the queue is precisely one level.

Here is the same flat walk as before, except that the snapshot makes it possible to say which level each value came from.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5from collections import deque6 7def tag_with_level(root):8    if root is None:9        return []10    tagged = []11    queue = deque([root])12    depth = 013    while queue:14        width = len(queue)              # this level, before anything is added15        for _ in range(width):16            node = queue.popleft()17            tagged.append((node.val, depth))18            if node.left:19                queue.append(node.left)20            if node.right:21                queue.append(node.right)22        depth += 123    return tagged24 25print(tag_with_level(T(1, T(2, T(4), T(5)), T(3))))

Code lab· 25 min

Level drills

Three readings of the same loop. level_sums returns the sum of each level. widest_level returns the number of nodes on the widest level. leftmost_per_level returns the first value on each level.

solution.py

Tests

tree = T(1, T(2, T(4), T(5)), T(3))print(level_sums(tree), level_sums(None))print(widest_level(tree), widest_level(None), widest_level(T(9)))print(leftmost_per_level(tree), leftmost_per_level(None))

Output

Run tests to see output.

Problem· 18 min

Binary Tree Level Order Traversal

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 18 min

Binary Tree Right Side View

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5from collections import deque6 7def visit_order(root):8 if root is None:9 return []10 order = []11 queue = deque([root])12 while queue:13 node = queue.popleft()14 order.append(node.val)15 if node.left:16 queue.append(node.left)17 if node.right:18 queue.append(node.right)19 return order20 21print(visit_order(T(1, T(2, T(4), T(5)), T(3))))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5from collections import deque6 7def tag_with_level(root):8 if root is None:9 return []10 tagged = []11 queue = deque([root])12 depth = 013 while queue:14 width = len(queue) # this level, before anything is added15 for _ in range(width):16 node = queue.popleft()17 tagged.append((node.val, depth))18 if node.left:19 queue.append(node.left)20 if node.right:21 queue.append(node.right)22 depth += 123 return tagged24 25print(tag_with_level(T(1, T(2, T(4), T(5)), T(3))))