Views and Layout

What is this?

Drawing a tree on paper means giving every node a column and a row. Once those exist, "what does it look like from above?" is a grouping question, not a traversal question — and the traversal only has to record coordinates.

The 301 difficulty is in the tie-breaks. When two nodes land on the same column and the same row, the specification decides the order, and getting that rule wrong produces output that is right almost everywhere.

💡 Fun fact: Vertical Order Traversal II differs from the easier vertical-order problem by exactly one clause: nodes sharing a column and a row are ordered by value, not by arrival. That single sentence is why BFS alone is no longer enough — arrival order is what BFS gives you for free, and here it is explicitly not the answer. The fix is to collect (col, row, value) triples and sort them, which makes the tie-break part of the data rather than part of the traversal.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: record a coordinate per node during one traversal, then let sorting or grouping produce the view. The traversal never needs to know what the view is.

1. Coordinates, then a sort

nodes = []                                     # (col, row, value)
def walk(node, row, col):
    if not node: return
    nodes.append((col, row, node.val))
    walk(node.left,  row + 1, col - 1)
    walk(node.right, row + 1, col + 1)

walk(root, 0, 0)
nodes.sort()                                   # col, then row, then value

Sorting the triples applies all three ordering rules at once, in exactly the stated priority — which is why building the key correctly removes the need for any comparator logic later. Group the sorted list by column and the answer falls out.

The alternative — BFS with a per-column list — gets column and row order for free but must still sort within a cell, so the triple-sort version is both shorter and easier to defend.

2. Stitching a level from the level above

Populating Next Right Pointers II drops the guarantee that the tree is perfect, so a node's right neighbour may be several subtrees away. The trick is to build each level using the links you have already established on the level above:

head = root
while head:
    dummy = Node(0); tail = dummy              # dummy absorbs the "is this the first child?" case
    node = head
    while node:                                # walk the current level via its own next pointers
        if node.left:  tail.next = node.left;  tail = tail.next
        if node.right: tail.next = node.right; tail = tail.next
        node = node.next
    head = dummy.next                          # the level just built

The dummy head is what removes every special case. Without it, each child has to ask "am I the first node on this level?" — and that question, asked in four places, is where the bugs live.

3. A 30-second worked example (the tie-break)

        1
       / \
      2   3          coordinates (col, row, value):
     / \ / \           4 → (-2, 2, 4)    2 → (-1, 1, 2)
    4  6 5  7          6 → ( 0, 2, 6)    1 → ( 0, 0, 1)
                       5 → ( 0, 2, 5)    3 → ( 1, 1, 3)
                       7 → ( 2, 2, 7)

column 0 holds three nodes:
   (0, 0, 1)   row 0
   (0, 2, 5)   row 2  ← 5 before 6: same column, same row, ordered by VALUE
   (0, 2, 6)   row 2

result: [[4], [2], [1, 5, 6], [3], [7]]

Nodes 6 and 5 share a cell. BFS would emit 6 first because it is the left child of the earlier node — and that is the wrong answer. The value tie-break puts 5 first.

4. Where you'll actually meet this

• UI and diagram layout. Assigning columns to nested elements is exactly this computation, deterministic tie-break included.
• Org-chart and family-tree rendering. Producing a stable left-to-right ordering that does not shift between renders.
• Compiler visualisation. Laying out syntax trees for debuggers and explorers.
• Linked structures in serialised formats. Sibling pointers make level traversal O(1)-space, which matters when trees are huge.
• Spreadsheet and grid mapping. Placing hierarchical data into rows and columns for display.

5. Problems in this chapter

▶ Vertical Order Traversal II

Group nodes by column, ordered by row, and by value within a cell. Collect (col, row, value) triples in one traversal and sort them.
Pattern: coordinates + sort. Target: O(n log n) time, O(n) space.

▶ Populating Next Right Pointers in Each Node II

Link each node to its right neighbour on a tree that is not perfect. Walk each level through the next pointers you already built, using a dummy head to stitch the level below.
Pattern: build level k+1 from level k. Target: O(n) time, O(1) extra space.

6. Common pitfalls 🚫

• Relying on BFS arrival order for the within-cell tie-break. The specification says by value, and those differ.
• Sorting only by column. All three keys matter, in order.
• Reaching for a queue in the next-pointer problem. That is O(width) space; the point of part II is doing it in O(1).
• Omitting the dummy head, which forces a "first child on this level?" check in several places.
• Assuming the tree is perfect. Part II exists precisely because it is not — a node's neighbour can be in a distant subtree.
• Tracking min and max columns and then iterating the range is fine, but only after the sort; doing it instead of sorting loses the tie-break.

7. Key takeaways

1. Record coordinates, then sort. The traversal should not know what the view is.
2. Put every ordering rule in the sort key — column, row, value — and no comparator logic is needed.
3. Read the tie-break clause carefully. It is the entire difference from the easier version.
4. Build each level from the one above to link siblings in O(1) space.
5. A dummy head deletes a class of edge cases wherever a list is being stitched.
6. Why interviewers like it: the traversal is trivial, so the whole signal is whether you implement the stated ordering exactly rather than the one BFS hands you.

Order: Vertical Order Traversal II → Populating Next Right Pointers in Each Node II.