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.
Worth knowing: Vertical Order Traversal II differs from the easier vertical-order problem (LeetCode 314) by exactly one clause: nodes sharing a column and a row are ordered by value, not by arrival. That is why plain BFS 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.
Core 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, so no comparator logic is needed later. Group the sorted list by column and the answer falls out. The cost is O(n log n), all of it in the sort. An empty tree returns [].
The alternative is BFS with a per-column list. It gives column and row order for free but still has to sort within a cell, so the triple-sort version is shorter and easier to defend.
2. Stitching a level from the level above
Populating Next Right Pointers in Each Node II (LeetCode 117) drops the guarantee that the tree is perfect, so a node's right neighbour may be under a different parent, several subtrees away. A BFS with a queue solves it in O(w) extra space, where w is the widest level. To get O(1), 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 several places, is where the bugs live. The loop visits each node once, so time is O(n) and extra space is O(1).
3. A 30-second worked example (the tie-break)
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, so column 0 reads [1, 5, 6] in the lesson's tree (root 1, left child 2 with right child 6, right child 3 with left child 5).
4. Where you'll actually meet this
- Tree and diagram layout. Placing a tree on a grid needs a column for each node and a stable order when two nodes share a cell. The value tie-break is that rule.
- Snapshot tests of rendered trees. If two nodes can share a cell, the output order must not depend on traversal order, or the test flakes.
- Level-by-level rendering. A pointer to the right neighbour turns each row of a tree into a plain linked-list walk, with no queue.
5. Problems in this chapter
Vertical Order Traversal II
Group nodes by column, ordered by row, and by value within a cell (LeetCode 987). Collect (col, row, value) triples in one traversal and sort them. The empty tree returns [].
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 of any shape (LeetCode 117). The lesson starts from BFS at O(w) space, then walks each level through the next pointers already built, using a dummy head to chain 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.
- Stopping at the queue in the next-pointer problem. BFS is a correct first answer at
O(w)space; the follow-up is doing it inO(1). - Omitting the dummy head, which forces a "first child on this level?" check in several places.
- Assuming the tree is perfect. The
node.right.next = node.next.leftshortcut from the perfect-tree version (LeetCode 116) fails here, because a node's neighbour can be under a different parent. - Forgetting the empty tree in the vertical-order problem, where
rootcan beNone. - Bucketing by column without sorting inside each
(col, row)cell. Buckets avoid the global sort, but the within-cell value order still has to be applied.
7. Key takeaways
- Record coordinates, then sort. The traversal should not know what the view is.
- Put every ordering rule in the sort key (column, row, value) and no comparator logic is needed.
- Read the tie-break clause carefully. It is the entire difference from the easier version.
- Build each level from the one above to link siblings in
O(1)space. - A dummy head deletes a class of edge cases wherever a list is being stitched.
- 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.
Vertical Order Traversal II
Core idea: Give every node a coordinate: the root is
(0, 0), a left child is(row + 1, col - 1), a right child is(row + 1, col + 1). The answer is the nodes sorted by(col, row, value)and grouped by column. The third key matters: two nodes on the same row and column are ordered by smaller value, not by the order your traversal found them. Collect triples in any traversal, sort once, group. Sorting dominates, so it is O(n log n).
Problem, rephrased
A diagram renderer flattens a hierarchy onto a grid before painting it column by column. You're given the root of a binary tree. The root sits at (0, 0), and a node at (row, col) puts its left child at (row + 1, col - 1) and its right child at (row + 1, col + 1).
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson