Binary Tree Vertical Order Traversal

Medium Trees & BST Views Original on LeetCode

Reported atMetaDoorDash

Binary Tree Vertical Order Traversal is a medium trees & bst problem solved with the views pattern. The best approach, optimal (bfs with column indices), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs + sort by column and row) up.

Problem

Given the root of a binary tree, return its values grouped by vertical column, with the columns listed from the leftmost to the rightmost. Place the root in column 0; a left child is one column to the left of its parent and a right child is one column to the right.

Inside each column, list the values from top to bottom. When two nodes share both the row and the column, the one that is further left in that row comes first.

Examples

Example 1

Input
root = [5, 2, 8, 1, 4, 7, 9]
Output
[[1], [2], [5, 4, 7], [8], [9]]
Why
4 (right child of 2) and 7 (left child of 8) both fall in the root's column, on the same row; 4 is further left in that row, so it comes first.

Example 2

Input
root = [10, null, 20, 15]
Output
[[10, 15], [20]]
Why
20 is one column to the right; its left child 15 steps back into column 0, two rows below the root, so it follows 10.

Example 3

Input
root = []
Output
[]
Why
An empty tree has no columns.

Constraints

  • The tree has 0 to 100 nodes.
  • -100 <= Node.val <= 100

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DFS + sort by column and row)O(n log n)O(n)
Optimal (BFS with column indices)O(n)O(n)

1Brute force (DFS + sort by column and row)

TimeO(n log n)The DFS is linear; sorting the n records dominates.
SpaceO(n)The record list and the output, plus recursion depth up to n.

Walk the tree with a preorder DFS and record (column, row, value) for every node. Sort the records by column, then by row, with a stable sort. Among nodes with equal column and row, preorder already lists the left one first, so stability keeps them in the required order. Then cut the sorted list into groups by column.

  1. dfs(node, col, row): record (col, row, val); recurse into left with (col - 1, row + 1) and right with (col + 1, row + 1).
  2. Stable-sort the records by (col, row).
  3. Scan them, starting a new inner list whenever the column changes.
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<int[]> recs = new ArrayList<>();
        dfs(root, 0, 0, recs);
        recs.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < recs.size(); i++) {
            if (i == 0 || recs.get(i)[0] != recs.get(i - 1)[0]) res.add(new ArrayList<>());
            res.get(res.size() - 1).add(recs.get(i)[2]);
        }
        return res;
    }

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

2Optimal (BFS with column indices)

TimeO(n)Each node is enqueued and dequeued once; columns form a contiguous range of at most n values.
SpaceO(n)The queue and the column lists hold every node once.

Breadth-first search visits nodes row by row and, within a row, from left to right, which is exactly the order required inside each column. Carry each node's column in the queue, append its value to that column's list, and remember the smallest and largest column seen. At the end, read the lists from the smallest column to the largest. No sorting is needed.

  1. If root is null, return [].
  2. Queue of (node, col) starting with (root, 0); a map col → list; minCol = maxCol = 0.
  3. Pop (node, col): append node.val to map[col]; update minCol / maxCol; push (left, col - 1) and (right, col + 1) when present.
  4. Return map[minCol], …, map[maxCol].
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Map<Integer, List<Integer>> cols = new HashMap<>();
        ArrayDeque<TreeNode> nodes = new ArrayDeque<>();
        ArrayDeque<Integer> colQ = new ArrayDeque<>();
        nodes.add(root);
        colQ.add(0);
        int minCol = 0, maxCol = 0;
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            int col = colQ.poll();
            cols.computeIfAbsent(col, c -> new ArrayList<>()).add(node.val);
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);
            if (node.left != null) {
                nodes.add(node.left);
                colQ.add(col - 1);
            }
            if (node.right != null) {
                nodes.add(node.right);
                colQ.add(col + 1);
            }
        }
        for (int c = minCol; c <= maxCol; c++) res.add(cols.get(c));
        return res;
    }
}

Edge cases to test

  • Empty tree
  • A single node
  • Two nodes in the same row and the same column (must appear left to right)
  • A node deeper in a left subtree that sits in a column to the right of a shallower node
  • A skewed tree (one node per column)

Hints

Hint 1

Give the root column 0; a left child is in column c - 1 and a right child in column c + 1. Group values by column.

Hint 2

Inside a column the order is by row (depth), and nodes on the same row keep their left-to-right order. Which traversal naturally produces nodes in row order, left to right?

Hint 3

Breadth-first search visits nodes exactly in that order, so appending to a column's list during BFS already gives the right order. Track the smallest and largest column to output columns without sorting them.

FAQ

What is the best time complexity for Binary Tree Vertical Order Traversal?

Optimal (BFS with column indices) runs in O(n) time and O(n) extra space. Each node is enqueued and dequeued once; columns form a contiguous range of at most n values.

Which pattern does Binary Tree Vertical Order Traversal use?

It is a trees & bst problem that uses the views pattern. Other problems with the same pattern: Top View of Binary Tree, Bottom View of Binary Tree, Left View of Binary Tree.

Is there a brute force solution for Binary Tree Vertical Order Traversal?

Yes. Brute force (DFS + sort by column and row) takes O(n log n) time and O(n) space. Walk the tree with a preorder DFS and record (column, row, value) for every node.

Which edge cases should I test for Binary Tree Vertical Order Traversal?

Empty tree; A single node; Two nodes in the same row and the same column (must appear left to right); A node deeper in a left subtree that sits in a column to the right of a shallower node; A skewed tree (one node per column).