Level order and tree views in Python

Why this lesson matters

The first two lessons walked a tree by going deep first. A depth-first walk follows one branch to its end before it looks at the next. That works well for sums and heights, but many real questions are about rows, not branches. What is on the second row of an org chart? Which pages are one click away from the home page? What would a person standing on the right side of a building see? Each of these asks for the nodes level by level, not branch by branch.

This lesson shows the walk that answers those questions, called level order or breadth-first search. You will use a queue to make it work, and you will see how the same walk gives you the four views of a tree that interviewers like to ask about. You will also see the shallowest-leaf question, which uses the same walk with an early stop. The breadth-first idea appears again in graphs in a later module, so the time you spend here pays off twice.

To follow along you need the tree class and the build helper from the first lesson, and you need to know that a None child means "no node here". Everything else is introduced below.

The idea: finish a row before the next

Picture a row of people at a cinema. The people in the front row stand up first, then the second row, then the third. Nobody in row three gets to stand before everybody in row two has stood. A tree walk that does the same thing is called level order, and the name breadth-first search, or BFS, means the same thing. Breadth-first means the walk spreads across the width of the tree before it goes down.

Compare this with the depth-first walks from the first lesson. Preorder, inorder and postorder dive down one side first. In a level order walk, you finish the whole row first. Both visit each node once, and both take O(n) time. They just visit the nodes in a different order, and the order decides which answers are easy to get.

To do the walk, you need a way to remember which nodes you have found but not yet visited. Suppose the root is visited. Its two children are now known, but they are not visited yet. They must wait in line. When you visit the first child, its own children join the end of the line, behind the second child. The second child is then visited before the grandchildren. This is exactly what a queue does.

Queues: first in, first out

A queue is a collection where you add items at the back and remove them from the front. The first item in is the first item out. Think of a line at a bus stop: the person who arrived first boards first. In Python, the right tool is collections.deque, a double-ended queue. You add with append and remove from the front with popleft.

A plain Python list can also act as a queue with pop(0), but that is slow. Removing the first item of a list moves every other item one place forward, so the cost grows with the length of the list. popleft on a deque takes the same short time no matter how long the queue is. Use deque for every queue in this module.

The methods you need are:

• append(x) adds x at the back.
• popleft() removes and returns the front item. It raises IndexError if the queue is empty.
• len(queue) gives the number of items.
• bool(queue) is False when the queue is empty, so while queue: runs as long as something is waiting.

Use the animation above to see the queue grow and shrink. Watch which node is at the front when it is removed, and which nodes join at the back.

Level order on the six-node tree

Here is the six-node tree from the first lesson. We will walk it level by level.

        1
       / \
      2   3
     / \   \
    4   5   6

Start with the root in the queue. Then repeat this step until the queue is empty: remove the front node, record its value, and add its children to the back of the queue. The children are added left first, then right. Because the queue is first in, first out, the nodes come out in the order they were added.

Here is the state of the queue after each step, with the front on the left.

Read the table carefully. At step 2, node 2 is removed and its children 4 and 5 join the back of the queue behind node 3. So node 3 is still next. Then node 3 is removed and its child 6 joins behind 4 and 5. The walk never goes deeper than the row it is on, until the row is finished. The final order 1, 2, 3, 4, 5, 6 is the level order, and it groups into rows as [1], [2, 3] and [4, 5, 6].

Grouping by level

A flat list of values loses the row structure. Often you need one list per row. The trick is to process exactly one row per round of an outer loop. Before the inner loop starts, read the size of the queue. That size is the number of nodes in the current row, because every node of the current row is in the queue and no node of the next row has been added yet.

round 1: queue holds [1]          size = 1  -> take 1 node
round 2: queue holds [2, 3]       size = 2  -> take 2 nodes
round 3: queue holds [4, 5, 6]    size = 3  -> take 3 nodes

Notice the important detail. The size is read once, before the inner loop. If the loop condition read len(queue) on every pass, the queue would grow while the loop ran, because children are added to the back. The loop would then keep taking nodes from the next row and mix the rows together. That mistake is common enough to have its own section below.

The for _ in range(size): form in the program below reads the size once, when the loop starts. The underscore _ is a name for a value you do not use.

The following program builds the list of rows for the six-node tree and for an empty tree.

Output:

six-node tree: [[1], [2, 3], [4, 5, 6]]
empty tree: []

The outer while loop runs once per level. Each pass creates a new list, fills it from the current row, and adds it to the result. The inner for loop runs exactly size times, so it takes exactly one row. The empty tree returns an empty list right away, because the first check stops the function before the queue is used.

Complexity of level order

Every node enters the queue once and leaves it once. Each append and popleft takes constant time, so the total time is O(n).

The space is the largest number of nodes waiting in the queue at one moment. That is roughly the width of the widest level. For a perfect tree with n nodes, the bottom level holds about half the nodes, so the queue can hold about n / 2 items. The space is therefore O(w), where w is the width. Compare this with the depth-first walks, which use O(h) space. For a balanced tree, w is large and h is small, so the two walks trade space differently. For a chain, the width is 1 and the queue never holds more than one node, while the recursive walk needs a frame for every node.

This trade-off is a good interview point. A breadth-first walk is cheap when the tree is tall and thin, and expensive when it is short and wide. A depth-first walk is the opposite.

Two more views: left and right

The left view of a tree is the list of nodes you see when you stand on the left side and look at each level. You see the first node of each row. The right view is what you see from the right side, which is the last node of each row. With the level lists ready, both views take one line each.

The views need a tree where the two sides differ. The six-node tree is too balanced to show it, so the next examples use a second tree, which we will call tree V. It has four levels.

        1
       / \
      2   3
     /     \
    4       5
   /
  6

Here the rows are [1], [2, 3], [4, 5] and [6]. Node 4 is on the left, node 5 is on the right of 3, and node 6 is the left child of 4.

The left view takes the first node of each row, which gives [1, 2, 4, 6]. The right view takes the last node of each row, which gives [1, 3, 5, 6]. The two lists share the root and the bottom node, and differ in the middle rows.

A word of caution: the right view is not the same as the list of right children. Node 6 is the last node on the bottom row and it is a left child, so it is part of the right view, even though nothing on its level is to the right of it. The right view shows the last node of each row, whatever side it is on.

The following program builds tree V and prints both views, along with a zigzag order. The zigzag order visits each row left to right, then the next row right to left, and so on, which is a common interview question.

Output:

levels:  [[1], [2, 3], [4, 5], [6]]
left:    [1, 2, 4, 6]
right:   [1, 3, 5, 6]
zigzag:  [[1], [3, 2], [4, 5], [6]]

The left_view and right_view functions are list comprehensions. A list comprehension builds a new list from a loop in one line. level[-1] is the last item of a list. Negative indexes count from the end, so -1 is the last item and -2 is the one before it.

The zigzag function reuses the level lists. It reverses every odd-numbered row, which are the second, fourth and so on. The range(1, len(rows), 2) call starts at index 1 and steps by 2. The reversal happens in place, which means the list inside the result changes. That is safe here because level_order made new lists for this call only.

Notice that the row [4, 5] is not reversed. It is the third row, which zigzag reads left to right. Only rows 2 and 4 are reversed.

The top view

The top view is what you see when you look down on the tree from above. For each horizontal position, you see the node that is closest to the top. Nodes that are hidden below another node in the same column do not show.

To find the positions, give each node a number called its column. The root is column 0. A left child is one column less than its parent, and a right child is one column more. Two nodes in the same column are directly above and below each other, and the one with the smaller depth covers the other. Level order visits nodes from the top down, so the first node met in each column is the visible one.

A Python dictionary keeps one value per key. The method setdefault(key, value) stores the value only when the key is missing, and it returns the stored value either way. That keeps the first node met in each column. A dictionary keeps the keys in the order they were added, which is not left to right, so the columns are sorted at the end.

Output:

top view of tree V: [6, 4, 2, 1, 3, 5]
top view of empty tree: []

Work through tree V by column. Node 1 is in column 0. Node 2 is in column -1, and node 3 is in column 1. Node 4 is a left child of 2, so it is in column -2. Its child 6 is a left child of 4, so it is in column -3. Node 5 is a right child of 3, so it is in column 2. Sorted by column from left to right, the first node in each column is 6, 4, 2, 1, 3 and 5, which is the output above. Node 6 is visible because it is the only node in column -3, and a deeper node still shows when no node above it shares its column.

The line sorted(first_in_column) gives the column numbers from smallest to largest. If you returned list(first_in_column.values()) without sorting, the answer would depend on the order the nodes were met, and that order is not left to right. The sort is part of the answer.

The sort costs O(k log k), where k is the number of columns, and k is never more than n. The walk itself is O(n). It is possible to avoid the sort by tracking the smallest and largest column and using a list indexed by column. That is a good follow-up in an interview, and it shows that you understand where the extra cost comes from.

The shallowest leaf

Some questions stop early. The shallowest leaf asks for the smallest depth at which any leaf appears. A depth-first walk must explore a whole branch to be sure it has found the shallowest leaf, but a breadth-first walk finds it first. The first leaf it meets, row by row, is the shallowest one.

The program below reads a tree from standard input, in the format from the first lesson, and prints the shallowest leaf depth.

import sys
from collections import deque
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build(tokens):
    if not tokens or tokens[0] == "null":
        return None
    root = TreeNode(int(tokens[0]))
    pending = deque([root])
    idx = 1
    while pending and idx < len(tokens):
        parent = pending.popleft()
        if idx < len(tokens) and tokens[idx] != "null":
            parent.left = TreeNode(int(tokens[idx]))
            pending.append(parent.left)
        idx += 1
        if idx < len(tokens) and tokens[idx] != "null":
            parent.right = TreeNode(int(tokens[idx]))
            pending.append(parent.right)
        idx += 1
    return root
 
 
def min_depth(root):
    if root is None:
        return 0
    queue = deque([root])
    depth = 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
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
    return depth
 
 
data = sys.stdin.read().split()
n = int(data[0])
tokens = data[1:1 + n]
root = build(tokens)
print("shallowest leaf depth:", min_depth(root))

Type this input into the program, with the two lines as they are:

5
1 2 3 null 4

Output:

shallowest leaf depth: 2

The tree from that input has root 1, with left child 2 and right child 3. Node 2 has no left child and a right child 4. Node 3 has no children, so it is a leaf at depth 2. Node 4 is a leaf too, but at depth 3. The walk reaches node 3 before node 4, because row 2 is finished before row 3 starts. It returns 2 as soon as it finds the leaf, so the rest of the tree is never visited. This is what makes the breadth-first walk the right tool for the question.

The function counts depth from 1 at the root, so a single node returns 1. An empty tree returns 0. The return depth at the end of the function is only reached if the queue runs out, which cannot happen for a valid non-empty tree, but it makes the function end on every path.

Notice what the depth-first version would do. It would go down the left side first, through node 2 to leaf 4 at depth 3, and only then check leaf 3 at depth 2. It would have to compare every branch to be sure. The breadth-first walk stops at the first leaf it meets.

Trace of the shallowest-leaf walk

Trace the walk on the tree from the input. The table shows the queue, the depth counter and what happens to each node. The depth counter goes up at the start of each round.

The walk stops at round two, inside the row, the moment it removes the leaf 3. Node 4 is still in the queue, but it does not matter because the answer is already known. This is also why the check for a leaf sits inside the inner loop, not after it.

Common mistakes and the errors they cause

Reading the queue size inside the loop

If the inner loop reads the live size of the queue on each pass, the rows are cut at the wrong place. Python's for _ in range(len(queue)): does not have this problem, because range reads the length once, when the loop starts. A while loop that compares a counter with len(queue) on every pass does have it. Here is that wrong version of level_order for the six-node tree and tree V.

The output is:

six: [[1, 2, 3], [4, 5], [6]]
tree V: [[1, 2], [3, 4], [5], [6]]

For the six-node tree, the loop takes node 1 and adds 2 and 3, so the queue holds 2 items. It takes 2 next, which adds 4 and 5, so the queue holds 3 items. The live length is now 3, so the loop takes 3 as well, and the first row becomes [1, 2, 3] instead of [1]. Node 3 lands in the first row, and the rows no longer match the tree's levels. The fix is to save the size in a variable before the loop, or to use for _ in range(len(queue)), as the working version does.

Adding a missing child to the queue

In Java, ArrayDeque refuses a null at the moment you add it. Python's deque accepts None without complaint, so the error appears later, when the code takes that None out and reads an attribute of it. The if check before each append is what prevents this. Here is the error you get when the check is missing.

from collections import deque
 
queue = deque()
queue.append(None)
node = queue.popleft()
print(node.val)

The output is:

Traceback (most recent call last):
  File "main.py", line 6, in <module>
    print(node.val)
          ^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'val'

The message names the attribute that was read, val, and the type that did not have it, NoneType. The line that matters is the last line of your own code, which is the read of node.val. The append that put the None into the queue is earlier in the file, so the crash happens far from the mistake. When you see NoneType in a tree walk, look for the place where a child was added without a check.

Using popleft on an empty queue

If you call popleft() on an empty deque, Python raises IndexError. The usual fix in tree code is to check while queue: before you take an item, so the call never happens on an empty queue.

from collections import deque
 
queue = deque()
queue.popleft()

The output is:

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    queue.popleft()
    ~~~~~~~~~~~~~^^
IndexError: pop from an empty deque

The message says what happened: the walk tried to take an item from a queue with nothing in it. The usual cause is a loop that does not check the queue first, or a loop that takes more items than it added.

Assuming the right view is the right children

The right view takes the last node of each row, not the children on the right side. In tree V, node 6 appears in the right view even though it is a left child. Test your right view on a tree where the bottom row sits on the left, as tree V does.

Using a stack instead of a queue

A stack is last in, first out. In Python, a list used with append and pop is a stack. If you use one in place of the queue, the walk goes deep first, and the rows come out wrong. The fix is to use deque with append and popleft, which gives first-in, first-out order. Check which pair of methods you are using, because pop() on a list and popleft() on a deque take from opposite ends.

Debugging walkthrough: the views are in the wrong order

Suppose your right view prints [1, 2, 5, 6] for tree V. The first value is right, the second is wrong. Node 2 is on the left, and it should not be in the right view. Start with the row lists. Print level_order(v) before you call right_view. You should see [[1], [2, 3], [4, 5], [6]]. If the second row shows [2, 3], the level order is right, and the bug is in right_view. If the second row shows [2], the bug is in level_order, which is missing node 3. Find the line where the children are added and check that the right child is appended in the right branch.

Once the levels look right, check the function that reads the last value. It should use level[-1], not level[0]. A wrong index is a common cause of the wrong view, and printing the row lists is the fastest way to find it.

Remove the print lines before you submit.

Worked example: a lopsided tree, one round at a time

The six-node tree and tree V are both fairly even. A lopsided tree shows more clearly what the queue holds at each round. Here is tree N. It has six nodes, but its left side is deeper than its right side.

        1
       / \
      2   5
     /     \
    3       6
   /
  4

Work out the queue by hand before you read the table. In each round, take the current row from the queue, then add the children of its nodes, left child first. The rows are the answer, and the queue holds the row that is about to be taken.

The rows are [1], [2, 5], [3, 6] and [4]. Notice that the queue never holds more than two nodes, even though the tree has six. The widest row is [2, 5] or [3, 6], which has two nodes, so the queue's width is 2. That is the space the walk needs, and it does not depend on how many rows the tree has.

Now compare this with the depth-first walks from the first lesson. A depth-first walk on the same tree would keep a path of at most four nodes on the call stack, because the deepest path is 1, 2, 3, 4. For this shape the two walks need about the same memory. The difference shows up on the two extreme shapes. A tall chain of 100,000 nodes has width 1, so the queue holds one node at a time, but its height is 100,000, so the recursive walk would fail on Python's recursion limit. A bushy tree of a million nodes has a wide bottom row, so the queue can hold about 500,000 nodes, while its height is about 20.

Keep this rule in mind when you choose a walk. Level order costs memory in proportion to the widest row. Depth-first costs memory in proportion to the tallest path.

Choosing between depth first and breadth first

A practical way to choose is to ask what the answer is built from. The table below sets the two families side by side for the questions in this module and the next.

The two families visit the same nodes in O(n) time. The difference is which answers come out naturally. A depth-first method returns a number for each subtree, and a breadth-first method returns a list for each row. Interviewers often ask you to say which one fits a problem before you write any code. Your answer should name the shape of the answer, not only the walk. For example, "the answer is one number per row, so I will use a queue" is a better answer than "I will use a queue".

Real-world uses

Breadth-first walks are everywhere that a question is about distance in steps. A social network finds friends of friends by walking out one step at a time, and the first time it reaches a person is the shortest chain of introductions. A web crawler visits pages level by level from a starting page, so it finds the pages closest to the start first. A maze solver in a game uses the same idea on a grid of squares: the first time the walk reaches the exit, it has found a shortest route. A company's org chart is a tree, and a manager who wants to know everyone on the third level of the chart asks a level-order question. In each case the queue is the same, and the question is always the same: which nodes are closest to the start?

Interview-style questions

Give the level order of a tree. Use a queue. Read the size before each round, and add each row as a list. O(n) time, O(w) space.

Find the minimum depth of a tree. Run a level-order walk and stop at the first leaf. The answer is the depth of that row. This is faster than a full walk when the tree is large and the shallow leaf is near the root.

Print the zigzag order. Build the level lists, then reverse every second list. Alternatively, use two stacks, one for each direction. The list version is easier to test.

Find the average of each level. Build the level lists and divide each row's sum by its length. In Python, / always gives a float, so 5 divided by 2 gives 2.5 and not 2.

Why do level order and depth-first walks use different space? Level order keeps the whole width of a level in the queue. Depth-first keeps only the path from the root. A wide tree needs a big queue. A tall tree needs a deep call stack.

Practice

Try each exercise before you open its answer. Use paper and the table method to predict the result, then check with code.

1. Predict the level order of the tree 1 2 3 null 4 5 (input format from the first lesson). Then write the code to check your answer. Hint: work out the children of each node in the order the values appear.

Show the answer

The input puts 1 at the root, with left child 2 and right child 3. Node 2 takes the next two positions, which are null and 4, so it has no left child and right child 4. Node 3 takes positions 5 and 6, which are 5 and nothing, so 3 has left child 5 and no right child. The level order is [[1], [2, 3], [4, 5]]. The builder reads the null as a position that adds no node.

2. Write def max_of_each_level(root): that returns the largest value on each row. Predict the answer for tree V before you run it. Hint: use max on each row list.

Show the answer

def max_of_each_level(root):
    return [max(level) for level in level_order(root)]

For tree V the answer is [1, 3, 5, 6]. The max function returns the largest item of a list. It raises ValueError on an empty list, but a level list is never empty, so this is safe here.

3. Write def average_of_each_level(root): that returns the average of each row. Predict the answer for the six-node tree. Hint: divide the sum by len(row).

Show the answer

def average_of_each_level(root):
    return [sum(level) / len(level) for level in level_order(root)]

For the six-node tree the answer is [1.0, 2.5, 5.0]. The first row is 1, the second is (2 + 3) / 2, which is 2.5, and the third is (4 + 5 + 6) / 3, which is 5. The / operator always gives a float in Python 3, so the first answer prints as 1.0 and not 1.

4. Write def count_nodes_at_depth(root, depth): using level order. Predict the answer for depth 2 of the six-node tree (3 nodes).

Show the answer

def count_nodes_at_depth(root, depth):
    rows = level_order(root)
    if depth < 0 or depth >= len(rows):
        return 0
    return len(rows[depth])

Depth is counted from 0 at the root. On the six-node tree, depth 2 is the third row, [4, 5, 6], so the answer is 3. The check guards against a depth past the bottom of the tree, and against a negative depth, which would otherwise count from the end of the list.

5. Write a version of top_view that uses a plain dict and returns the values in the order they were inserted, without sorting. Explain why this gives the wrong answer for the top view, even though the values are right.

Show the answer

Remove the sorted call and return list(first_in_column.values()). On tree V the nodes are inserted in level order, so the values come out as [1, 2, 3, 4, 5, 6], not [6, 4, 2, 1, 3, 5]. The values are right, but the order is by the time each column was first seen, not by column. The top view needs the columns from left to right, so the sort is required.

6. Explain in one sentence why the shallowest-leaf walk can return before it has visited every node, and why a depth-first walk cannot.

Show the answer

A breadth-first walk visits nodes in order of depth, so the first leaf it meets is at the smallest depth, and it can return at once. A depth-first walk may dive down a long branch before it looks at a shallow leaf on another branch, so it cannot know a leaf is the shallowest until it has checked the other branches too.

7. Write def is_full_levels(root): that returns True when every row except possibly the last is full. Predict the answer for the six-node tree (True) and tree V (False).

Show the answer

def is_full_levels(root):
    rows = level_order(root)
    for r in range(len(rows) - 1):
        if len(rows[r]) != 2 ** r:
            return False
    return True

Row r is full when it holds 2 ** r nodes. The six-node tree has rows of sizes 1, 2 and 3, so the first two rows are full and the last row may be partial, giving True. Tree V has rows of sizes 1, 2, 2 and 1, and row 2 holds 2 nodes but should hold 4, so it returns False.

8. Predict what the zigzag order of the six-node tree is, then check it with code. Hint: row 2 is reversed.

Show the answer

The six-node tree has levels [1], [2, 3] and [4, 5, 6]. Zigzag reverses row 2, so the answer is [[1], [3, 2], [4, 5, 6]]. Row 3 is read left to right, so it is unchanged.

9. Write def bottom_left_value(root): that returns the first value on the last row. Predict the answer for tree V (6).

Show the answer

def bottom_left_value(root):
    rows = level_order(root)
    if not rows:
        return None
    return rows[-1][0]

For tree V the last row is [6], so the answer is 6. The function returns None for an empty tree. That is a choice you should state in your code, because a real value could also be None in other programs.

10. Write a program that reads a tree from the input format and prints the number of rows. Use 7 and 1 2 3 4 5 null 6. Expected output: rows: 3.

Show the answer

Use the builder and level_order from this lesson, with the input 7 and 1 2 3 4 5 null 6. Print rows: followed by len(level_order(root)). The output is rows: 3, since the rows are [1], [2, 3] and [4, 5, 6].

11. Write the rightmost value on each row using a queue that stores only the last node of each round, and test it against the right view from this lesson. Explain why you do not need to build the whole row list.

Show the answer

def rightmost_per_round(root):
    result = []
    if root is None:
        return result
    queue = deque([root])
    while queue:
        last = None
        for _ in range(len(queue)):
            last = queue.popleft()
            if last.left is not None:
                queue.append(last.left)
            if last.right is not None:
                queue.append(last.right)
        result.append(last.val)
    return result

The variable last keeps the node taken last in each round, which is the rightmost node of that row. The function does not build the row lists, so it uses less memory. It gives [1, 3, 5, 6] for tree V, the same as the right view. The deque class needs from collections import deque at the top of the file.

12. Predict the output of level_order_broken for tree V before you run it, and say how many rows it returns.

Show the answer

The loop reads the live length of the queue on every pass, so it stops at a different place from the row's end. For tree V the output is [[1, 2], [3, 4], [5], [6]], as shown in the common mistakes section. It returns 4 rows, but the rows have sizes 2, 2, 1 and 1, while the true levels have sizes 1, 2, 2 and 1. The fix is to read the size once before the loop, so that each round takes exactly one row.

What you now know

• Level order visits a tree one row at a time, using a queue. Nodes join the back of the queue and leave the front, so each row finishes before the next one starts.
• Use collections.deque with append and popleft for a queue. A list with pop(0) works, but it is slow on long queues.
• Read the queue size once at the start of each round, so that each round takes exactly one row.
• The left view takes the first node of each row, the right view takes the last, and the zigzag order reverses every second row.
• The top view uses a column number for each node and keeps the first node met in each column, then sorts the columns.
• The shallowest leaf is the first leaf a level-order walk reaches, so the walk can stop there.
• A breadth-first walk costs O(n) time and O(w) space, where w is the width of the widest row.