Problem statement

Place the root of a binary tree at position (row, col) = (0, 0). For a node at (row, col), its left child sits at (row + 1, col - 1) and its right child at (row + 1, col + 1).

The vertical order traversal lists the tree column by column, from the leftmost column to the rightmost. Within one column the nodes go from top to bottom (increasing row); nodes that share both the row and the column are listed by increasing value.

Return the vertical order traversal as a list of columns.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: Column -1 holds 9; column 0 holds 3 (row 0) then 15 (row 2); column 1 holds 20; column 2 holds 7.

Example 2

Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 5 and 6 both sit at row 2, column 0, so the smaller value comes first.

Example 3

Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: Swapping 5 and 6 in the tree does not change the answer: ties are broken by value, not by position.

Constraints

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

Hints for Vertical Order Traversal of a Binary Tree

1. Hint 1

   Give every node its (row, col) with one traversal — the order of the traversal does not matter once you have the coordinates.

2. Hint 2

   The required order is a sort: by column, then by row, then by value.

3. Hint 3

   Sort the triples (col, row, value) and cut the sorted list wherever the column changes.

How to solve Vertical Order Traversal of a Binary Tree

The traversal order is defined entirely by each node's coordinates and value, so compute (col, row, value) for every node and sort. The columns are then consecutive runs of the sorted list.

Approach

1. Traverse the tree (DFS or BFS), passing (row, col) down: the left child gets (row + 1, col - 1), the right (row + 1, col + 1).
2. Record a triple (col, row, value) for each node.
3. Sort the triples lexicographically.
4. Walk the sorted triples, starting a new column whenever col differs from the previous triple's, and append each value to the current column.

Why it works

Lexicographic order on (col, row, value) is exactly the order the statement asks for: columns left to right, inside a column top to bottom, and value as the final tie-break for nodes sharing a position. Columns are contiguous in that order, so cutting at column changes yields the lists.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• A plain BFS that appends values in visit order breaks the tie between nodes at the same row and column — they must be ordered by value.
• Nodes in the same column but on different rows are ordered by row, not by value.
• Column indices are negative to the left of the root; offset them or sort rather than indexing an array with them.

Reference solution

Python

from typing import List, Optional

def verticalTraversal(root: Optional[TreeNode]) -> List[List[int]]:
    items = []
    stack = [(root, 0, 0)]
    while stack:
        node, row, col = stack.pop()
        if node is None:
            continue
        items.append((col, row, node.val))
        stack.append((node.left, row + 1, col - 1))
        stack.append((node.right, row + 1, col + 1))
    items.sort()
    result = []
    for i, (col, _, val) in enumerate(items):
        if i == 0 or col != items[i - 1][0]:
            result.append([])
        result[-1].append(val)
    return result

Java

public static int[][] verticalTraversal(TreeNode root) {
    List<int[]> items = new ArrayList<>();
    collectVertical(root, 0, 0, items);
    items.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[2], b[2]));
    List<List<Integer>> cols = new ArrayList<>();
    for (int i = 0; i < items.size(); i++) {
        if (i == 0 || items.get(i)[0] != items.get(i - 1)[0]) cols.add(new ArrayList<>());
        cols.get(cols.size() - 1).add(items.get(i)[2]);
    }
    int[][] result = new int[cols.size()][];
    for (int i = 0; i < cols.size(); i++) result[i] = cols.get(i).stream().mapToInt(Integer::intValue).toArray();
    return result;
}

static void collectVertical(TreeNode node, int row, int col, List<int[]> items) {
    if (node == null) return;
    items.add(new int[] { col, row, node.val });
    collectVertical(node.left, row + 1, col - 1, items);
    collectVertical(node.right, row + 1, col + 1, items);
}

C++

vector<vector<int>> verticalTraversal(TreeNode* root) {
    vector<array<int, 3>> items;
    function<void(TreeNode*, int, int)> walk = [&](TreeNode* node, int row, int col) {
        if (!node) return;
        items.push_back({col, row, node->val});
        walk(node->left, row + 1, col - 1);
        walk(node->right, row + 1, col + 1);
    };
    walk(root, 0, 0);
    sort(items.begin(), items.end());
    vector<vector<int>> result;
    for (size_t i = 0; i < items.size(); i++) {
        if (i == 0 || items[i][0] != items[i - 1][0]) result.push_back({});
        result.back().push_back(items[i][2]);
    }
    return result;
}

JavaScript

var verticalTraversal = function(root) {
    var items = [];
    var stack = [[root, 0, 0]];
    while (stack.length > 0) {
        var top = stack.pop();
        var node = top[0], row = top[1], col = top[2];
        if (node === null) continue;
        items.push([col, row, node.val]);
        stack.push([node.left, row + 1, col - 1]);
        stack.push([node.right, row + 1, col + 1]);
    }
    items.sort(function (a, b) { return a[0] - b[0] || a[1] - b[1] || a[2] - b[2]; });
    var result = [];
    for (var i = 0; i < items.length; i++) {
        if (i === 0 || items[i][0] !== items[i - 1][0]) result.push([]);
        result[result.length - 1].push(items[i][2]);
    }
    return result;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard