Vertical order, boundary and top view in Python

Why this lesson matters

Stand to the side of a drawn tree and look at it from one end. Some nodes sit directly above others in a column. Some are hidden behind nodes closer to you. A question like "list the nodes you would see from the left, column by column" sounds like a puzzle, but it is a common interview question, and it is a good test of whether you can organise a tree walk around a question about position rather than about depth.

This lesson uses one idea for three questions. Each node gets a column number. Nodes with the same column number go into the same group, and the groups are read in left-to-right order by sorting the column numbers. The three answers are the vertical order (every group, in full), the top view (only the first node in each group), and the boundary (the outline of the tree).

To follow along, you need to know how a queue works and how a node's left and right attributes link to its children. The lesson uses the queue walk from the level order lesson of this module, so the code below repeats only what it needs. The code uses collections.deque for the queue and collections.defaultdict for the groups.

Columns: one number for each node

Give the root column 0. For every node, its left child is one column to the left of it, so the column number goes down by one. Its right child is one column to the right, so the column number goes up by one. Every node therefore gets a number from its path of left and right moves.

Here is a tree with nine nodes. We will use it for every example in this lesson. Call it tree V.

            1
         /     \
        2       3
       / \     / \
      4   5   6   7
           \       \
            8       9

Work down the tree, and write each node's column next to it.

Two things stand out. Node 5 and node 6 are both in column 0, even though they are on different sides of the tree. Node 8 is in column 1, the same as node 3, but node 8 is two rows below it. Nodes in the same column can be at different depths, and nodes at the same depth can share a column.

The table has a useful pattern. Each step down moves the depth by one and the column by one, so the depth and the column always have the same remainder when divided by two. A node at depth 3 always has an odd column, and a node at depth 2 always has an even column. You can use this to check your work.

A dictionary sorted by column keeps the groups in order

The answers we want are lists of nodes, one list for each column, ordered from the leftmost column to the rightmost. A dictionary stores pairs of keys and values. Since Python 3.7, a dictionary remembers the order in which the keys were added, not the order of the numbers. So the code sorts the column numbers at the end, with sorted, and reads the groups in that order.

The code creates the groups like this:

columns = defaultdict(list)

The key is the column number. The value is a list of the node values in that column. A defaultdict makes an empty list the first time a key is used, so the code can add to a column without checking whether it exists:

columns[column].append(node.val)

When the groups are read at the end, [columns[c] for c in sorted(columns)] gives the leftmost column first, because the sorted keys go from negative to positive.

The walk must be breadth-first

The lists in each column must be in order from top to bottom, and nodes at the same depth must be in left-to-right order. A walk that goes one level at a time, using a queue, gives this order for free. Nodes of depth 1 are visited before nodes of depth 2, and so on. Within one depth, the queue holds nodes left to right, because each node adds its left child before its right child.

So each queue entry needs two things: the node, and its column. A tuple, which is a fixed group of values, holds both, as (node, column). The walk starts with the root in column 0, then for each entry it adds the value to its column group and queues the children with column numbers one less (left) or one more (right).

Worked example 1: the vertical order of tree V

Here is the full function. It is the code that produced the output in this example, and the program in the code section below runs it.

def vertical_order(root):
    columns = defaultdict(list)
    if root is None:
        return []
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        columns[column].append(node.val)
        if node.left is not None:
            queue.append((node.left, column - 1))
        if node.right is not None:
            queue.append((node.right, column + 1))
    return [columns[c] for c in sorted(columns)]

Trace the queue for the first few steps. The front of the queue is on the left.

Step 5 is where the order matters. Node 5 joins column 0 after node 1. Node 6 joins column 0 after node 5, because node 5 was removed from the queue before node 6. Both are at depth 2, and node 5 is on the left, so the queue gives them to us in that order. Node 8 is added to the queue at step 5 and removed later, so it joins column 1 after node 3, which is shallower.

The program prints:

vertical order of V: [[4], [2], [1, 5, 6], [3, 8], [7], [9]]

The first list is column -2, the second is column -1, and so on, up to column 3. Column 0 is [1, 5, 6], which is top to bottom and left to right within the same depth.

Worked example 2: a column with nodes at different depths

Tree W is below. Node 11 is the right child of node 10, which is the right child of node 2. Node 12 is the right child of node 11, and node 13 is the left child of node 12.

            1
         /     \
        2       3
       / \     / \
      4  10   6   7
           \
            11
              \
               12
              /
             13

The vertical order of tree W, from the same function, is:

[[4], [2], [1, 10, 6], [3, 11, 13], [7, 12]]

Column 1 contains node 3 (depth 1), node 11 (depth 3) and node 13 (depth 5). Column 2 contains node 7 (depth 2) and node 12 (depth 4). In both columns, the shallower node comes first. The walk gives this order because it works one depth at a time, so the shallow node 3 is read before the deeper nodes 11 and 13 that sit under the left side of the root.

Top view: the first node in each column

The top view is what you see when you look down on the tree from above. For each column, only the highest node is visible, because a node below it in the same column is hidden. So the top view is the first node that the walk reaches in each column.

The method is the same as the vertical order, with one change. Instead of a list per column, keep one value per column. The method setdefault(key, value) stores the value only when the key is not already in the dictionary, and it returns the stored value either way:

def top_view(root):
    top = {}
    if root is None:
        return []
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        top.setdefault(column, node.val)
        if node.left is not None:
            queue.append((node.left, column - 1))
        if node.right is not None:
            queue.append((node.right, column + 1))
    return [top[c] for c in sorted(top)]

Because the walk is breadth-first, the first node stored in a column is always the shallowest one. In column 0 of tree V, that is node 1, which is above nodes 5 and 6. The output for tree V is:

top view of V: [4, 2, 1, 3, 7, 9]

Each value is the first node seen in its column, read from left to right. Node 8 is not in the top view, because node 3 is above it in column 1.

Boundary: the outline of the tree

The boundary is the outline you see if you walk around the outside of the tree. This lesson uses one common definition, stated here so the answers can be checked. The boundary is made of four parts, in this order:

1. The root.
2. The left edge, from the top down. These are the nodes you reach by going left whenever you can, going right only when there is no left child. Leaves (nodes with no children) are not included.
3. Every leaf, from left to right.
4. The right edge, from the bottom up. These are the nodes you reach by going right whenever you can, going left only when there is no right child. Leaves are not included. The root is not included again.

The leaves in part 3 include leaves deep inside the tree, not only the ones on the outer edge. So a leaf is counted once, in its place from left to right.

The code has one function for each part. Each function is recursive, which means it calls itself on the next node down. The left edge function adds the node before its children, so the top comes first. The right edge function adds the node after its children, so the bottom comes first.

def is_leaf(n):
    return n.left is None and n.right is None
 
 
def boundary(root):
    out = []
    if root is None:
        return out
    out.append(root.val)
    if is_leaf(root):
        return out
    add_left(root.left, out)
    add_leaves(root, out)
    add_right(root.right, out)
    return out
 
 
def add_left(n, out):
    if n is None or is_leaf(n):
        return
    out.append(n.val)
    if n.left is not None:
        add_left(n.left, out)
    else:
        add_left(n.right, out)
 
 
def add_leaves(n, out):
    if n is None:
        return
    if is_leaf(n):
        out.append(n.val)
        return
    add_leaves(n.left, out)
    add_leaves(n.right, out)
 
 
def add_right(n, out):
    if n is None or is_leaf(n):
        return
    if n.right is not None:
        add_right(n.right, out)
    else:
        add_right(n.left, out)
    out.append(n.val)

Worked example 3: the boundary of tree V

Start with the root, 1. Then add_left runs on node 2. Node 2 is not a leaf, so it is added. Its left child is 4, so the walk goes to 4. Node 4 is a leaf, so it is skipped. The left edge is [2].

Next, add_leaves runs on the root and visits every leaf from left to right. Node 4 is the first leaf. Node 5 has a child, so it is not a leaf. Its right child is 8, which is a leaf. Then comes node 6, then node 9, which is the right-most leaf under node 7. The leaves are [4, 8, 6, 9].

Last, add_right runs on node 3. Node 3 has a right child, 7, so the walk goes to 7. Node 7 has a right child, 9, which is a leaf and is skipped by the check at the top. Then the function adds node 7 on the way back up, and after that it adds node 3. The right edge is [7, 3].

Putting the four parts together gives [1, 2, 4, 8, 6, 9, 7, 3]. The program prints:

boundary of V          = [1, 2, 4, 8, 6, 9, 7, 3]

Node 5 is not in the output. It is neither on the left edge nor on the right edge, and it is not a leaf. Node 8 is included only because it is a leaf.

The program below builds trees V and W, and prints the three answers for V, then the vertical order and the depth-first variant from the mistakes section for W.

Output:

vertical order of V: [[4], [2], [1, 5, 6], [3, 8], [7], [9]]
top view of V: [4, 2, 1, 3, 7, 9]
boundary of V: [1, 2, 4, 8, 6, 9, 7, 3]
vertical order of W: [[4], [2], [1, 10, 6], [3, 11, 13], [7, 12]]
dfs columns of W: [[4], [2], [1, 10, 6], [11, 13, 3], [12, 7]]

Common mistakes

Mistake 1: relying on the order a dictionary was filled in

A Python dictionary keeps the keys in the order they were added. That is not the same as sorted order. If the code builds the groups in the order it meets the nodes, and then reads the keys without sorting, the columns come out in the wrong order. In the example below, the keys were added as 16, 1 and 0, and reading them back gives that same order.

The output is:

keys in the order added: [16, 1, 0]
keys sorted: [0, 1, 16]

Columns can be negative, and the walk meets them in an order that depends on the tree, so the sort is what puts them left to right. Use sorted whenever the order of the keys matters.

Mistake 2: a depth-first walk

A depth-first walk visits a whole branch before the next one. It can add a deep node to a column before a shallow node in the same column is added. The dfs_columns function in the program above is that walk, and the output shows the problem on tree W:

dfs columns of W: [[4], [2], [1, 10, 6], [11, 13, 3], [12, 7]]

The depth-first version puts node 12 (depth 4) before node 7 (depth 2) in column 2, because it walks the whole left side of the root before it reaches node 7. Column 1 shows the same problem: node 3 comes last instead of first. The fix is to use the queue walk from worked example 1.

Mistake 3: reading a child without a check

Every child may be None. Reading an attribute of a None child stops the program. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
lonely = TreeNode(42)
print(lonely.left.val)

The output is:

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

The file path in the traceback depends on where you save the file. The message names the attribute that was read from None, which is val. The caret points at lonely.left.val, and the expression lonely.left is the one that holds None. Check if node.left is not None before reading node.left.val, as the walks above do before they queue a child.

Mistake 4: setdefault where the bottom view needs a plain assignment

The top view needs the first node in each column. If the code uses a plain assignment instead of setdefault, each new node in a column overwrites the old one, and the last node in each column is kept. That gives the bottom view, not the top view. The exercises below ask you to write the bottom view on purpose. In the top view, the difference is one method call, so check which one you used.

Practice

Exercise 1: predict the vertical order

Move node 8 so that it is the right child of node 4, instead of the right child of node 5. Node 5 has no children now. Predict the vertical order, then check the answer.

Show the answer

[[4], [2, 8], [1, 5, 6], [3], [7], [9]]

Node 8 is in column -1, one step to the right of node 4 in column -2. Node 8 is at depth 3, and node 2 is at depth 1 in the same column, so node 2 comes first. Node 3 is the only node in column 1 now, because node 8 has left column 1.

Exercise 2: write the bottom view

The bottom view is the last node in each column when the tree is read in breadth-first order. Write it using the same walk as the top view.

Show the answer

Use a plain assignment instead of setdefault:

def bottom_view(root):
    bottom = {}
    if root is None:
        return []
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        bottom[column] = node.val
        if node.left is not None:
            queue.append((node.left, column - 1))
        if node.right is not None:
            queue.append((node.right, column + 1))
    return [bottom[c] for c in sorted(bottom)]

For tree V, the output is [4, 2, 6, 8, 7, 9]. Column 0 gives node 6, which is the last node at that column in breadth-first order, because node 6 comes after node 5 in the queue.

Exercise 3: boundary of a chain

Tree K is a chain of three nodes: 1 has right child 2, and 2 has right child 3. Predict its boundary, using the four parts from this lesson.

Show the answer

[1, 3, 2]

The root is 1. The left edge is empty, because node 1 has no left child. The only leaf is 3. The right edge, from the bottom up, is 2, because node 2 is not a leaf and node 3 is a leaf that is not counted again. The output is [1, 3, 2].

Exercise 4: a small tree with a tie

Here is a tree with four nodes. The root is 1. Its left child is 2, and its right child is 3. Node 2 has a right child 4. Node 3 has a left child 5. Give the vertical order and explain why 4 comes before 5.

Show the answer

[[2], [1, 4, 5], [3]]

Node 4 is in column 0 at depth 2, and node 5 is also in column 0 at depth 2. Both are at the same depth, so the walk decides their order by position. Node 4 is under the left side of the root and node 5 is under the right side, so node 4 is added to the queue first.

Summary

• Give the root column 0, a left child one less, and a right child one more.
• Group the nodes in a dictionary keyed by column, then read the columns in sorted order so the groups come out from left to right.
• A breadth-first walk with a queue gives each column its nodes from top to bottom, and nodes at the same depth come left to right.
• The top view keeps the first node in each column, and the bottom view keeps the last one.
• The boundary is the root, the left edge top down, the leaves left to right, and the right edge bottom up, with leaves counted once.
• A depth-first walk gives a wrong order inside a column, and a dictionary's insertion order is not the left-to-right order.