</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Vertical order plan: coordinate each node, then break ties by value

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)

Worked example: column 0 orders 5 before 6 by value; result array

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 in O(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.left shortcut 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 root can be None.
  • 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

  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.

Populating Next Right Pointers in Each Node II

Core idea: Use the level you have already linked to build the next one. Walk level k along its own next pointers and chain together its children as you meet them, so level k+1 gets linked without a queue. A dummy head node anchors each new chain, which removes the "is this the first child on the level?" special case. Extra space is O(1) even though the tree can be any shape.

Problem, rephrased

A tournament bracket UI draws one round per row. Some entrants got byes, so the bracket is a general binary tree: a match may feed from one match below it, two, or none, and the first matches don't all sit on the same row. Each node has left, right and an extra next pointer that starts as None. The renderer wants to slide sideways along a row without climbing back up through parents.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.