Tree Views, in depth: right, left, top and bottom views with BFS, DFS, tie rules and a worked example

Definitions: depth, horizontal distance and ties

Fix the definitions before writing code, because interview statements and libraries differ on edge cases.

• Depth: the root has depth 0, and a child has its parent's depth plus 1.
• Horizontal distance (hd): the root has hd 0, a left child has its parent's hd minus 1, and a right child has its parent's hd plus 1. Nodes with equal hd form one vertical column.
• Right view: for each depth, the rightmost node at that depth. Left view: the leftmost.
• Top view: for each hd from leftmost to rightmost column, the node with the smallest depth. If two nodes share column and depth, take the one met first in left-to-right level order.
• Bottom view: for each hd, the node with the largest depth. If two nodes share column and depth, take the one met last in level order. That is the rightmost of the tied pair.

The tie rules are conventions, and the bottom-view one in particular varies between problem setters. State yours in code and tests. Note that hd is a drawing coordinate, not a geometric one: a left child's right child sits in the same column as its grandparent, which is why deep nodes can surface in the top or bottom view far from where you might expect.

Left and right views

Left and right views need one fact per node: its depth. Breadth-first search with a queue visits nodes level by level from left to right, so if you process each level as a batch, the first node in the batch is the left view and the last is the right view:

from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def levels(root):
    """Yield each level as a list of nodes, left to right."""
    if root is None:
        return
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):          # exactly the nodes of this level
            node = q.popleft()
            level.append(node)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        yield level

def right_view(root):
    return [level[-1].val for level in levels(root)]

def left_view(root):
    return [level[0].val for level in levels(root)]

The for _ in range(len(q)) line is the whole trick. It snapshots the queue length at the start of the level, so children appended during the loop wait for the next batch. Forgetting it, and checking while q alone, produces one list with every node in it.

The depth-first alternative visits children right-first and records the first node it reaches at each new depth. Because it goes right before left, the first arrival at depth d is the rightmost node there. With an explicit stack, push left before right so right pops first:

def right_view_dfs(root):
    out, stack = [], [(root, 0)] if root else []
    while stack:
        node, depth = stack.pop()
        if depth == len(out):            # first arrival at this depth
            out.append(node.val)
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))   # popped first
    return out

The depth == len(out) test works because a depth-first search reaches depths in increasing order along any path, so the output list grows exactly one entry per new depth. Swap the two push lines for the left view. Both versions are O(n) time. BFS uses O(w) extra space, where w is the widest level, and the DFS uses O(h), where h is the height. Pick DFS for wide, shallow trees and BFS for tall, narrow ones.

Top and bottom views in one pass

Top and bottom views need two facts per node: hd to pick the column and depth to rank nodes within it. BFS supplies depth implicitly, since it never visits a deeper node before a shallower one, so a single pass computes both views:

def top_and_bottom_view(root):
    if root is None:
        return [], []
    top, bottom = {}, {}
    q = deque([(root, 0)])               # (node, hd)
    while q:
        node, hd = q.popleft()
        top.setdefault(hd, node.val)     # first seen in level order wins
        bottom[hd] = node.val            # last seen in level order wins
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    lo, hi = min(top), max(top)          # columns are contiguous
    return ([top[h] for h in range(lo, hi + 1)],
            [bottom[h] for h in range(lo, hi + 1)])

Two details make this O(n) rather than O(n log n). First, the columns are contiguous, because every edge changes hd by exactly 1, so there are no gaps between the minimum and maximum hd. You can therefore walk range(lo, hi + 1) instead of sorting keys. Second, setdefault and plain assignment encode the tie rules directly: first-in-level-order for the top, last-in-level-order for the bottom. In Java the usual TreeMap<Integer, Integer> gives sorted columns for O(n log n), which is fine in practice. A HashMap plus tracked min and max gives O(n).

The preorder top-view bug

The most common wrong answer is a recursive top view that records the first node seen in each column during preorder:

def top_view_wrong(root):
    seen = {}
    def go(node, hd):
        if node is None:
            return
        seen.setdefault(hd, node.val)    # first in PREORDER, not by depth
        go(node.left, hd - 1)
        go(node.right, hd + 1)
    go(root, 0)
    return [seen[h] for h in sorted(seen)]

Preorder finishes the whole left subtree before touching the right one. If a deep node in the left subtree drifts right into a column that a shallow node in the right subtree also occupies, the deep node is recorded first and wins. The fix is to carry depth and keep the shallowest node per column:

def top_view_dfs(root):
    best = {}                            # hd -> (depth, val)
    def go(node, hd, depth):
        if node is None:
            return
        if hd not in best or depth < best[hd][0]:
            best[hd] = (depth, node.val)
        go(node.left, hd - 1, depth + 1)
        go(node.right, hd + 1, depth + 1)
    go(root, 0, 0)
    return [best[h][1] for h in sorted(best)]

The strict < keeps the earlier preorder node on a depth tie, and preorder meets tied nodes left to right, so this matches the BFS tie rule. The bottom view by DFS needs >= on depth to let later nodes win ties. Recursion depth equals tree height, so a degenerate tree of 100,000 nodes exceeds Python's default recursion limit. Prefer the BFS version unless you have a reason not to.

Worked example

Use the tree in Figure 1. Root 1 has children 2 and 3. Node 2 has children 4 and 5. Node 3 has left child 9 and right child 6. Node 5 has right child 7, and 7 has right child 8. Assigning coordinates as (depth, hd): 1 is (0, 0), 2 is (1, -1), 3 is (1, +1), 4 is (2, -2), 5 is (2, 0), 9 is (2, 0), 6 is (2, +2), 7 is (3, +1) and 8 is (4, +2).

Trace the BFS for columns +1 and +2. The queue visits 1; then 2 and 3, setting top[+1] = 3; then 4, 5, 9 and 6, setting top[+2] = 6; then 7, which updates only bottom[+1]; then 8, which updates only bottom[+2]. The wrong DFS visits 1, 2, 4, 5, 7, 8 and only then 3 and 6, so 7 and 8 claim columns +1 and +2 first. Every assertion below passes on this tree:

root = Node(1,
            Node(2, Node(4), Node(5, None, Node(7, None, Node(8)))),
            Node(3, Node(9), Node(6)))
assert right_view(root) == right_view_dfs(root) == [1, 3, 6, 7, 8]
assert left_view(root) == [1, 2, 4, 7, 8]
assert top_and_bottom_view(root) == ([4, 2, 1, 3, 6], [4, 2, 9, 7, 8])
assert top_view_dfs(root) == [4, 2, 1, 3, 6]
assert top_view_wrong(root) == [4, 2, 1, 7, 8]   # the bug, pinned

This tree is a good regression fixture because it breaks each naive shortcut at least once. Keep it in your test file alongside an empty tree, a single node, a left-only chain and a right-only chain.

Related problems

Tree views are a small family inside a larger one, and recognising the family helps with unseen variants:

• Vertical order traversal outputs every node per column, not one. The same BFS with defaultdict(list) solves it. Some problem statements sort tied nodes by value rather than by level order, so read the tie rule.
• Boundary traversal combines the left boundary, the leaves and the reversed right boundary. It resembles the side views but is a different set. Node 7 in the example is in the left view yet is not on the left boundary.
• Level-indexed problems, such as level averages, zigzag order or the largest value per level, all reuse the levels() generator above. The same batching idea powers populating next pointers.

Outside interviews, the hd-and-depth model appears in tree layout for UIs: column assignment for drawing org charts, collapsing overlapping nodes, or choosing which labels stay visible when a rendered tree is viewed edge-on. In those settings you usually need the whole column map, not just the extreme node, so compute it once and derive views from it.

Failure modes

Mistakes that pass small tests and fail later:

• Preorder top or bottom view without depth. Correct on balanced trees, wrong when one subtree reaches into another's columns. Pin the example above as a test.
• Missing level snapshot. Reading len(q) inside the loop condition rather than once per level merges levels.
• Unstated tie rule. Two correct implementations disagree on bottom-view ties. Write the rule in a docstring and a test.
• Recursion depth. Recursive solutions crash on degenerate trees in Python and on very deep trees in Java. Use iteration or raise the limit deliberately.
• Sorting when unnecessary. sorted(seen) is O(c log c) over c columns. Walking range(lo, hi + 1) is linear and also documents the contiguity invariant.
• Empty input. min() of an empty dict raises. Guard root is None first.

What to do next

1. Type out levels(), right_view and left_view from memory and run them on the example tree.
2. Implement top_and_bottom_view and confirm both outputs match the table.
3. Run top_view_wrong on the same tree and explain the difference without looking.
4. Write the DFS bottom view with >= on depth and check it against BFS on 1,000 random trees.
5. Extend the BFS to full vertical order traversal and state its tie rule.
6. Rewrite the BFS version in Java with a HashMap and min and max trackers, for O(n).
7. Review building trees from traversals to generate test trees from compact inputs.