LeetCode 987: Vertical Order Traversal of a Binary Tree

Problem Restatement

We are given the root of a binary tree.

Each node has a coordinate:

We need to return the vertical order traversal of the tree.

That means:

1. Visit columns from left to right.
2. Inside each column, visit nodes from top to bottom.
3. If multiple nodes have the same row and column, sort them by value.

The number of nodes is in the range [1, 1000], and node values are in the range [0, 1000].

Input and Output

Function shape:

def verticalTraversal(root: Optional[TreeNode]) -> list[list[int]]:
    ...

Examples

Example 1:

root = [3, 9, 20, None, None, 15, 7]

Tree:

      3
     / \
    9   20
       /  \
      15   7

Coordinates:

Group by column:

Answer:

[[9], [3, 15], [20], [7]]

Example 2:

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

Tree:

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

Coordinates:

At coordinate (2, 0), both 5 and 6 appear. Since they share the same row and column, they are sorted by value.

Answer:

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

First Thought: Traverse and Group by Column

A natural idea is to do DFS or BFS and put every node into a dictionary by column.

For example:

column -> list of node values

But this is not enough.

Inside a column, nodes must be ordered by row. Also, if two nodes have the same row and column, they must be ordered by value.

So we need to remember three pieces of information for every node:

column, row, value

Key Insight

If we collect every node as a tuple:

(column, row, value)

then Python’s default tuple sorting gives exactly the order we need:

1. Sort by column.
2. If columns tie, sort by row.
3. If rows tie, sort by value.

After sorting, all nodes from the same column are next to each other. We can scan the sorted list and group values by column.

Algorithm

Use DFS.

For each node:

1. Record (column, row, node.val).
2. Visit the left child with (row + 1, column - 1).
3. Visit the right child with (row + 1, column + 1).

After DFS:

1. Sort all recorded tuples.
2. Scan the sorted tuples.
3. Start a new group whenever the column changes.
4. Append node values to the current column group.
5. Return all groups.

Correctness

The DFS visits every node exactly once and records its correct coordinate. The root starts at (0, 0). For every node at (row, column), the algorithm assigns the left child to (row + 1, column - 1) and the right child to (row + 1, column + 1), matching the coordinate definition.

After all nodes are recorded, sorting tuples (column, row, value) orders nodes first by column from left to right, then by row from top to bottom, and then by value for nodes at the same position.

The final scan groups consecutive tuples with the same column. Since sorting places all equal-column tuples together and already orders them correctly within the column, each group is exactly one vertical column in the required order.

Therefore, the algorithm returns the correct vertical traversal.

Complexity

Let n be the number of nodes.

The recursion stack can be O(h), where h is the tree height, but the tuple list dominates in the general complexity.

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> list[list[int]]:
        nodes = []

        def dfs(node: Optional[TreeNode], row: int, col: int) -> None:
            if node is None:
                return

            nodes.append((col, row, node.val))

            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        nodes.sort()

        answer = []
        current_col = None

        for col, row, value in nodes:
            if col != current_col:
                answer.append([])
                current_col = col

            answer[-1].append(value)

        return answer

Code Explanation

We collect all positioned nodes here:

nodes = []

The DFS receives both coordinates:

def dfs(node: Optional[TreeNode], row: int, col: int) -> None:

If the node is missing, there is nothing to record:

if node is None:
    return

For a real node, record:

nodes.append((col, row, node.val))

The order is important. We store column first because the final output is grouped by column.

Then visit children with their coordinate changes:

dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)

After collecting all nodes, sort them:

nodes.sort()

This sorts by column, then row, then value.

Finally, group values by column:

for col, row, value in nodes:
    if col != current_col:
        answer.append([])
        current_col = col

    answer[-1].append(value)

Testing

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.verticalTraversal(root1) == [[9], [3, 15], [20], [7]]

    root2 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3, TreeNode(6), TreeNode(7)),
    )
    assert s.verticalTraversal(root2) == [[4], [2], [1, 5, 6], [3], [7]]

    root3 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(6)),
        TreeNode(3, TreeNode(5), TreeNode(7)),
    )
    assert s.verticalTraversal(root3) == [[4], [2], [1, 5, 6], [3], [7]]

    root4 = TreeNode(1)
    assert s.verticalTraversal(root4) == [[1]]

    print("all tests passed")

run_tests()