Vertical Order Traversal of a Binary Tree

hardAmazon-tagged: Trees & Matrix (mock day)73 stepsJava · Python · C++

Report nodes column by column, left to right; within a column, top to bottom, and nodes at the same position sorted by value. Give every node a (column, row) coordinate with DFS, then sort all (col, row, value) triples and group by column.

▶ Watch the animated trace

Traced input: root = [3, 9, 20, null, null, 15, 7] → [[9], [3, 15], [20], [7]]. Original problem: leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(n)

Sorting the n triples dominates.

Key idea

Root is (col 0, row 0); left child is col − 1, right child is col + 1, both row + 1.
Sort by column, then row, then value: this handles the tie rule.
Group consecutive triples with the same column.

Common mistakes

BFS order alone doesn't sort ties at the same position by value.
Confusing this with LeetCode 314, which keeps BFS order for ties.

Solution

Java

List<List<Integer>> verticalTraversal(TreeNode root) {
    List<int[]> nodes = new ArrayList<>();
    collect(root, 0, 0, nodes);
    nodes.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
    List<List<Integer>> res = new ArrayList<>();
    int prevCol = Integer.MIN_VALUE;
    for (int[] t : nodes) {
        if (t[0] != prevCol) {
            res.add(new ArrayList<>());
            prevCol = t[0];
        }
        res.get(res.size() - 1).add(t[2]);
    }
    return res;
}

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

Python

def verticalTraversal(root: Optional[TreeNode]) -> List[List[int]]:
    nodes = []

    def collect(node: Optional[TreeNode], col: int, row: int) -> None:
        if not node: return
        nodes.append((col, row, node.val))
        collect(node.left, col - 1, row + 1)
        collect(node.right, col + 1, row + 1)

    collect(root, 0, 0)
    nodes.sort()
    res, prev_col = [], None
    for col, _, val in nodes:
        if col != prev_col:
            res.append([])
            prev_col = col
        res[-1].append(val)
    return res

C++

void collect(TreeNode* node, int col, int row, vector<array<int, 3>>& out) {
    if (!node) return;
    out.push_back({col, row, node->val});
    collect(node->left, col - 1, row + 1, out);
    collect(node->right, col + 1, row + 1, out);
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
    vector<array<int, 3>> nodes;
    collect(root, 0, 0, nodes);
    sort(nodes.begin(), nodes.end());
    vector<vector<int>> res;
    int prevCol = INT_MIN;
    for (auto& [col, row, val] : nodes) {
        if (col != prevCol) {
            res.emplace_back();
            prevCol = col;
        }
        res.back().push_back(val);
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Tie at the same position 5 and 6 share (col 0, row 2) and are sorted by value.	`root = [1, 2, 3, 4, 6, 5, 7]`	`[[4], [2], [1, 5, 6], [3], [7]]`
Single node One column.	`root = [1]`	`[[1]]`