Vertical Order Traversal of a Binary Tree

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement

Given the root of a binary tree, return its vertical order traversal. Nodes are grouped by column: the root is at column 0, a left child is at column col - 1, a right child is at column col + 1. Within a column, nodes at higher rows (closer to root) come first. If two nodes are at the same row and column, the smaller value comes first.

Example 1:

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

        3
       / \
      9  20
         / \
        15  7

Output: [[9], [3, 15], [20], [7]]
Columns -1: [9], 0: [3, 15], 1: [20], 2: [7]

Example 2:

Input: root = [1, 2, 3, 4, 6, 5, 7]

        1
       / \
      2   3
     / \ / \
    4  6 5  7

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

Note: at column 0, nodes 1 (row 0), 5 (row 2), and 6 (row 2) all stack. At row 2, column 0 has both 5 and 6, so the smaller value (5) comes first.

Constraints:

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

Difficulty: Hard (but appears on OA as a Medium variant) LC: 987 Round: OA / Technical R1

---

Pattern Recognition

• What is the input structure? A binary tree.
• What are we optimizing? Group and order nodes by column, then row, then value.
• What pattern does this fit? Tree traversal (DFS or BFS) that tags each node with (col, row) coordinates, followed by a sort.
• Why does this pattern fit? Column index is a natural "bucket" but the ties at the same column must break on row, then on value. A global sort on (col, row, val) tuples handles all three ordering rules in one step.

A common trap is to use BFS and push values into a map keyed by column, assuming BFS row order sorts them correctly. That works for the simpler Binary Tree Vertical Order Traversal (LC 314) but fails LC 987's value tiebreaker.

---

Approach

Brute Force — BFS with Column Map

BFS with a queue of (node, col). Push values into colMap[col] in BFS order. Return columns sorted by key.

This works for LC 314 but fails LC 987 because two nodes at the same row and column must be ordered by value, not by BFS insertion order.

Time: O(n log n) for column sort. Space: O(n). Why insufficient for LC 987: Ties within the same row/column are not broken by value.

Optimal — DFS + Global Sort

Key Insight: Every node has a unique tuple (col, row, val) that fully encodes its ordering. Collect all tuples, then sort by (col asc, row asc, val asc). Group by column to produce the answer.

Step-by-step:

1. DFS (or BFS) the tree, passing down row and col. Root starts at row = 0, col = 0.
2. For each visited node, push (col, row, val) into a list.
3. Sort the list by col, then row, then val.
4. Walk the sorted list and emit a new sub-list each time col changes.

Time: O(n log n) — sort dominates. Space: O(n) — tuples + recursion stack.

---

Walkthrough

Trace on Example 2 tree:

        1 (row=0, col=0)
       / \
      2   3
     / \ / \
    4  6 5  7

Collected tuples (col, row, val):

node	row	col	tuple
1	0	0	(0, 0, 1)
2	1	-1	(-1, 1, 2)
4	2	-2	(-2, 2, 4)
6	2	0	(0, 2, 6)
3	1	1	(1, 1, 3)
5	2	0	(0, 2, 5)
7	2	2	(2, 2, 7)

After sorting by (col, row, val):

tuple
(-2, 2, 4)	col=-2 group starts
(-1, 1, 2)	col=-1 group starts
(0, 0, 1)	col=0 group starts
(0, 2, 5)	value tiebreaker: 5 before 6
(0, 2, 6)
(1, 1, 3)	col=1 group starts
(2, 2, 7)	col=2 group starts

Answer: [[4], [2], [1, 5, 6], [3], [7]].

Notice the value tiebreaker at (0, 2): node 5 comes before node 6 because 5 < 6, even though in BFS 6 would be visited first.

---

Implementation

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(v: number = 0, l: TreeNode | null = null, r: TreeNode | null = null) {
        this.val = v;
        this.left = l;
        this.right = r;
    }
}

function verticalTraversal(root: TreeNode | null): number[][] {
    const nodes: [number, number, number][] = []; // [col, row, val]

    const dfs = (node: TreeNode | null, row: number, col: number) => {
        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);

    // Sort by col, then row, then val — all ascending.
    nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);

    const result: number[][] = [];
    let currentCol = Number.NEGATIVE_INFINITY;
    for (const [col, , val] of nodes) {
        if (col !== currentCol) {
            result.push([]);
            currentCol = col;
        }
        result[result.length - 1].push(val);
    }
    return result;
}

C++

#include <vector>
#include <algorithm>
#include <tuple>
#include <functional>
#include <climits>

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

std::vector<std::vector<int>> verticalTraversal(TreeNode* root) {
    std::vector<std::tuple<int, int, int>> nodes; // col, row, val

    std::function<void(TreeNode*, int, int)> dfs = [&](TreeNode* n, int row, int col) {
        if (!n) return;
        nodes.emplace_back(col, row, n->val);
        dfs(n->left, row + 1, col - 1);
        dfs(n->right, row + 1, col + 1);
    };
    dfs(root, 0, 0);

    std::sort(nodes.begin(), nodes.end()); // lexicographic on tuple is exactly what we want

    std::vector<std::vector<int>> result;
    int currentCol = INT_MIN;
    for (auto& [col, row, val] : nodes) {
        if (col != currentCol) {
            result.push_back({});
            currentCol = col;
        }
        result.back().push_back(val);
    }
    return result;
}

Watch out:

1. Forgetting the value tiebreaker. BFS order does not equal value order. LC 987 explicitly requires the value sort at equal row+col.
2. Using a hash map keyed on col and appending in BFS order. Produces wrong output for LC 987. Use tuples + sort instead.
3. Empty tree. root == null should return [].

---

Complexity Analysis

	Time	Space
Optimal (DFS + Sort)	O(n log n)	O(n)

Bottleneck: The sort over n tuples is O(n log n). If you used a BFS per row with a priority queue at each column, you could amortize better but the asymptotics stay the same.

---

Edge Cases

1. Single node — returns [[root.val]].
2. Skewed left / skewed right tree — each node is in its own column.
3. Two children with identical values at the same (row, col) — the value tiebreaker makes the order deterministic; duplicate values just appear twice.
4. Wide tree with many columns — the result grouping scan handles this naturally.
5. Negative column indices — sort handles them because tuples compare lexicographically.

---

Related Problems

• LC 314 — Binary Tree Vertical Order Traversal — Same layout, but BFS order suffices (no value tiebreaker). Simpler.
• LC 102 — Binary Tree Level Order Traversal — Group by row instead of column.
• LC 199 — Binary Tree Right Side View — The rightmost node per row, which is a projection along the column axis.
• LC 513 — Find Bottom Left Tree Value — The leftmost node in the deepest row.

---

OA Strategy Notes

In a 75-minute OA with two problems, this is a likely "heavier" second problem. Budget 35-40 minutes. The risk is implementation bugs, not the algorithm: forgetting to sort by value, off-by-one on the column grouping, or mishandling null root. Write the DFS carefully and test on a small tree before submitting.

---

What is Expected at Each Level

Junior: Identify tree traversal. Write a DFS and group by column. May miss the value tiebreaker and need a hint.

Mid-level: Arrive at the (col, row, val) tuple + sort solution directly. Correctly identify that BFS-ordered insertion fails LC 987.

Senior: Discuss O(n log n) vs the heap-per-column alternative. Note that LC 314 vs LC 987 differ only in the tiebreaker. Mention that for very wide trees, a two-pass min-col/max-col scan then bucket emission is slightly more cache-friendly.