HardHash TableTreeDepth-First SearchBreadth-First SearchSortingBinary TreeUpdated Sep 2026

987. Vertical Order Traversal of a Binary Tree

Asked at Salesforce

Difficulty

Hard

Time

O(n log n)

Space

O(n)

Pattern

Hash Table

Companies

1

Problem

You are given the root of a binary tree. Imagine placing each node on a grid. The root sits at position (row, col) = (0, 0). A left child moves one step down and one step left, so it is at (row + 1, col - 1). A right child moves one step down and one step right, so it is at (row + 1, col + 1).

Now look at the tree column by column. Start with the leftmost column and move right to the rightmost column. Inside one column, list the nodes from top to bottom (smaller row first).

Sometimes two nodes land on the exact same (row, col) cell. When that happens, put the smaller value first. Return the answer as a list of lists: one inner list per column, in left-to-right order.

Columns and rows on a grid

positions-10120129320157Root 3 at (0,0); 9 at (1,-1); 20 at (1,1); 15 at(2,0); 7 at (2,2)
Each node gets a (row, col) cell; the answer reads columns left to right, top to bottom inside each column.

Constraints

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

Examples

Example 1
Inputroot = [3,9,20,null,null,15,7]
Output[[9],[3,15],[20],[7]]
WhyNode 9 is alone in column -1. Column 0 holds 3 (row 0) and 15 (row 2), so 3 comes before 15. Node 20 is alone in column 1, and node 7 is alone in column 2.
Example 2
Inputroot = [1,2,3,4,5,6,7]
Output[[4],[2],[1,5,6],[3],[7]]
WhyColumn 0 has three nodes: 1 at row 0, then 5 and 6 both at row 2. Since 5 and 6 share the same cell, we sort them by value, giving 5 before 6.
Example 3
Inputroot = [1,2,3,4,6,5,7]
Output[[4],[2],[1,5,6],[3],[7]]
WhyThis tree is the same as the previous one except nodes 5 and 6 are swapped in the input. They still land on the same cell, so the value rule puts 5 before 6 again and the answer does not change.

Asked At

1 companies
CompanyDifficulty
SalesforceHardView all Salesforce questions →

How to Think About It

1

Use DFS or BFS to assign column and row coordinates to every node

2

Store nodes in a map keyed by column, then by row within each column

3

For nodes at the same column and row, sort them by value before adding to result

4

BFS is preferred to naturally process nodes top-to-bottom within each column

5

Collect all (col, row, value) triples and sort by col, then row, then value

Optimal Approach

Perform a BFS or DFS traversal, tracking the column and row of each node. Store each node as a tuple of (column, row, value) in a list. Sort the list by column first, then by row, then by value. Group consecutive entries with the same column into sub-lists to form the result. BFS is preferred because it naturally processes nodes level by level, giving a more intuitive row ordering. The key insight is that three-dimensional sorting (col, row, value) produces the correct output.

Collect triples, then sort

BFS: push (root, col=0, row=0)record (col, row, val) per nodesort triples by col, row, valgroup equal cols into listsFour simple steps turn the tree into the answer.sorted triples(-1,1,9)(0,0,3)(0,2,15)(1,1,20)(2,2,7)After sorting, equal columns sit next to each other in theright order.key = (col, row, value)group by col → [[9],[3,15],[20],[7]]
BFS records (col, row, value) for every node; sorting by col, then row, then value gives the answer directly.
ComplexityTime O(n log n)Space O(n)We collect n triples and sort them; the sort dominates, and the list of triples plus the queue take linear space.

What Trips People Up in Real Interviews

1

Clarify the tie-breaking rule: same column and row means sort by value

2

Ask whether it is vertical traversal (column-first) or top-down (row-first)

3

Discuss BFS vs DFS: BFS gives natural row ordering, DFS does not

4

Mention that column can be negative (left subtree), zero (root), positive (right)

5

Talk about edge case: empty tree returns empty list

Solution Code

O(n log n) time
from collections import defaultdict, deque

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> list[list[int]]:
        nodes = []
        queue = deque([(root, 0, 0)])
        while queue:
            node, col, row = queue.popleft()
            if node:
                nodes.append((col, row, node.val))
                queue.append((node.left, col - 1, row + 1))
                queue.append((node.right, col + 1, row + 1))

        nodes.sort()
        result = []
        current_col = None
        for col, row, val in nodes:
            if col != current_col:
                result.append([])
                current_col = col
            result[-1].append(val)
        return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Vertical Order Traversal of a Binary Tree problem?

Given a binary tree, return the vertical order traversal of its nodes values. For each column from left to right, nodes are ordered by their row (top to bottom), and nodes at the same position are sorted by value. This requires coordinating column, row, and value ordering simultaneously.

How do you solve Vertical Order Traversal of a Binary Tree?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Vertical Order Traversal of a Binary Tree?

Vertical Order Traversal of a Binary Tree is asked at Salesforce. It is a hard difficulty problem.

What are common mistakes on Vertical Order Traversal of a Binary Tree?
  • Clarify the tie-breaking rule: same column and row means sort by value
  • Ask whether it is vertical traversal (column-first) or top-down (row-first)
  • Discuss BFS vs DFS: BFS gives natural row ordering, DFS does not
  • Mention that column can be negative (left subtree), zero (root), positive (right)
  • Talk about edge case: empty tree returns empty list