Vertical Order Traversal of a Binary Tree — LC 987 FAANG Coordinate Pattern

Problem Statement#

Given the root of a binary tree, return the vertical order traversal of its nodes' values. For each node at position (row, col), its left child is at (row + 1, col - 1) and right child at (row + 1, col + 1). The root is at (0, 0). The vertical order is column-by-column from leftmost to rightmost. Within the same column, order by row; if multiple nodes share (row, col), order by value ascending.

Constraints:

• The number of nodes is in the range [1, 1000]
• 0 <= Node.val <= 1000

Input:  root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Input:  root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
        Note: 5 and 6 share (row=2, col=0), tie-break by value.

Why This Problem Matters#

LeetCode 987 Vertical Order Traversal is a Hard-difficulty interview question asked at Meta, Amazon, Google, and Microsoft. Unlike LC 314 (its easier sibling) which only requires column ordering, 987 adds the value tie-breaker — a detail that trips up candidates who default to plain BFS.

This problem is a great signal of attention to detail: stronger candidates ask "what about ties?" before coding; weaker ones produce passing-then-failing solutions on edge cases. It also tests data-structure choice — a TreeMap of columns (Java) or a sorted dict (Python) trades implementation complexity for clarity.

The pattern recurs in tree visualization, layout algorithms (e.g., D3 tree diagrams), and any "project a tree into a 2D grid" task.

The Core Insight#

Each node has a unique sortable triple (col, row, val). Collect all triples, sort once, then group by column. The sort respects all three ordering constraints in a single pass.

DFS or BFS both work, but BFS naturally enforces row order within a column (no value tie-break, but row tie-break is free). Because the value tie-breaker requires explicit sorting anyway, DFS is fine too.

The cleanest solution: DFS to collect (col, row, val), sort by (col, row, val), then group by col into output rows.

Visual Dry Run#

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

         1 (0,0)
        / \
   (1,-1)2  3 (1,1)
       / \ / \
  (2,-2)4 6 5 7
        (2,0)(2,0)(2,2)

Triples sorted by (col, row, val):

Note: 5 sorts before 6 by value despite same (row, col). Output: [[4],[2],[1,5,6],[3],[7]].

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def verticalTraversal(self, root):
        nodes = []  # (col, row, val)
        def dfs(node, row, col):
            if not node:
                return
            nodes.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)
        dfs(root, 0, 0)
        nodes.sort()  # lexicographic sort handles all three keys
        cols = defaultdict(list)
        for col, row, val in nodes:
            cols[col].append(val)
        return [cols[c] for c in sorted(cols)]

var verticalTraversal = function(root) {
    const nodes = [];
    const dfs = (node, row, col) => {
        if (!node) return;
        nodes.push([col, row, node.val]);
        dfs(node.left,  row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    };
    dfs(root, 0, 0);
    nodes.sort((a, b) =>
        a[0] - b[0] || a[1] - b[1] || a[2] - b[2]
    );
    const cols = new Map();
    for (const [col, _, val] of nodes) {
        if (!cols.has(col)) cols.set(col, []);
        cols.get(col).push(val);
    }
    return [...cols.keys()].sort((a, b) => a - b).map(c => cols.get(c));
};

Time: O(n log n) — dominated by the sort. Space: O(n) for the triple list and column map.

Common Mistakes#

• Skipping the value tie-breaker — passes LC 314 but fails LC 987 hidden tests.
• Using BFS without sorting same-position nodes by value — silently wrong.
• Using (col, row) tuple as a dict key with a list of values — still need to sort the value list per cell.
• Forgetting to sort columns when building output — produces unordered output rows.
• Hardcoding column range — columns can be large for very wide trees.

Interview Tips#

• Confirm the value tie-breaker explicitly: "If two nodes share (row, col), do I sort by value?"
• State complexity: O(n log n) due to sort.
• Discuss alternatives: TreeMap+BFS, but explain that the explicit sort is simpler and equally fast.
• Note that DFS and BFS both work, but DFS is shorter to write.

Follow-up Questions#

• LC 314 (no tie-break)? BFS suffices; group by column as you go.
• Reduce sort to O(n)? Bucket-sort by column (rows still need sort) — tricky and rarely beats sort.
• Output row indices alongside values? Append (row, val) instead of just val.
• Find leftmost-bottom node by column? Track per column the entry with max row, min val.
• Stream input (no parent pointer)? Same DFS with carried (row, col).

Key Takeaways#

• LeetCode 987 is a Hard-difficulty FAANG tree question asked at Meta, Amazon, and Google.
• Each node maps to a unique triple (col, row, val); sort lexicographically by all three.
• The value tie-breaker on shared (row, col) is what distinguishes LC 987 from LC 314.
• Time complexity O(n log n) dominated by the sort.
• Space complexity O(n) for triples and the column groupings.
• BFS alone does not solve LC 987 — explicit sort is required for the value tie-break.
• The pattern transfers to tree visualization, layout, and 2D projection algorithms.