LeetCode 987 - Vertical Order Traversal of a Binary Tree

The problem asks us to compute the vertical order traversal of a binary tree. In simpler terms, we are asked to “look at the tree from the side” and collect the nodes that align in the same vertical column.

leetcodehardhash-tabletreedepth-first-searchbreadth-first-searchsortingbinary-tree

LeetCode Problem 987

Difficulty: 🔴 Hard
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Sorting, Binary Tree

Solution

Problem Understanding

The problem asks us to compute the vertical order traversal of a binary tree. In simpler terms, we are asked to “look at the tree from the side” and collect the nodes that align in the same vertical column. Each node has a position defined by (row, col) where row is its depth (root at 0) and col is its horizontal offset from the root (root at 0). Moving left decreases the column by 1, and moving right increases it by 1.

The input is the root of a binary tree, which may contain between 1 and 1000 nodes. Node values range from 0 to 1000. The output should be a list of lists, where each inner list contains the node values for one vertical column, sorted first by row (top to bottom) and, for nodes sharing the same row and column, by value (ascending). The output columns themselves must be sorted from the leftmost column to the rightmost column.

Important edge cases include a tree with only the root, nodes with duplicate values in the same row and column, and a completely skewed tree (all nodes either left or right). These can trip up implementations if sorting and column handling are not carefully managed.

Approaches

The brute-force approach would be to traverse the tree and store nodes in a 2D array indexed by column. We would have to scan the tree to determine the minimum and maximum column indices first. Then, for each column, sort nodes by row and then value. While this works, it is cumbersome, requires multiple passes, and involves repeated sorting for each column.

The optimal approach leverages a single traversal (BFS or DFS) to collect nodes along with their (row, col) coordinates. We can store nodes in a dictionary keyed by col, with a list of tuples (row, val) as values. After the traversal, we sort each list by (row, val) and then extract only the values. BFS is preferred as it naturally traverses level by level, maintaining row order automatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(N log N + C log C) O(N + C) Store nodes in a 2D array by column, sort each column by row and value
Optimal O(N log N) O(N) BFS or DFS to collect (row, col, val) tuples, then sort each column list by row and value

Algorithm Walkthrough

  1. Initialize a dictionary columns to map each column index to a list of (row, value) tuples. Also initialize a queue q for BFS, containing (root, row=0, col=0).
  2. Perform BFS: while the queue is not empty, dequeue a node along with its (row, col) position. Append (row, node.val) to columns[col].
  3. If the node has a left child, enqueue (node.left, row+1, col-1). If it has a right child, enqueue (node.right, row+1, col+1).
  4. After BFS is complete, collect all column indices, sort them from smallest to largest.
  5. For each column index, sort the list of (row, val) tuples first by row, then by value, and extract only the node values.
  6. Return the list of sorted columns as the final vertical order traversal.

Why it works: BFS ensures we process nodes level by level, which preserves row order. Using (row, val) tuples allows for correct ordering when multiple nodes share the same row and column. Sorting keys and extracting values at the end guarantees both vertical and top-to-bottom order, handling all edge cases including duplicates.

Python Solution

# 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
from collections import defaultdict, deque
from typing import List, Optional

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        columns = defaultdict(list)
        q = deque([(root, 0, 0)])  # node, row, col

        while q:
            node, row, col = q.popleft()
            columns[col].append((row, node.val))
            if node.left:
                q.append((node.left, row + 1, col - 1))
            if node.right:
                q.append((node.right, row + 1, col + 1))

        result = []
        for col in sorted(columns.keys()):
            sorted_col = sorted(columns[col], key=lambda x: (x[0], x[1]))
            result.append([val for row, val in sorted_col])

        return result

The implementation starts by initializing a queue for BFS and a dictionary for columns. Each node is stored along with its (row, col) coordinates. After BFS, columns are processed in order, and each list is sorted by row and value. The final result is built by extracting the node values in the correct order.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "sort"

func verticalTraversal(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    type NodeInfo struct {
        row int
        val int
    }

    columns := map[int][]NodeInfo{}
    queue := []struct {
        node *TreeNode
        row  int
        col  int
    }{{root, 0, 0}}

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        columns[curr.col] = append(columns[curr.col], NodeInfo{curr.row, curr.node.Val})

        if curr.node.Left != nil {
            queue = append(queue, struct {
                node *TreeNode
                row  int
                col  int
            }{curr.node.Left, curr.row + 1, curr.col - 1})
        }
        if curr.node.Right != nil {
            queue = append(queue, struct {
                node *TreeNode
                row  int
                col  int
            }{curr.node.Right, curr.row + 1, curr.col + 1})
        }
    }

    cols := make([]int, 0, len(columns))
    for k := range columns {
        cols = append(cols, k)
    }
    sort.Ints(cols)

    result := make([][]int, 0, len(cols))
    for _, col := range cols {
        nodes := columns[col]
        sort.Slice(nodes, func(i, j int) bool {
            if nodes[i].row != nodes[j].row {
                return nodes[i].row < nodes[j].row
            }
            return nodes[i].val < nodes[j].val
        })
        vals := make([]int, len(nodes))
        for i, n := range nodes {
            vals[i] = n.val
        }
        result = append(result, vals)
    }

    return result
}

The Go implementation follows the same BFS approach. The main differences include using slices instead of deque, defining a struct for (row, val) information, and using sort.Slice to sort nodes within each column. Nil root handling is explicit, and slices are used for dynamic storage.

Worked Examples

Example 1: root = [3,9,20,null,null,15,7]

Node Row Col Columns dictionary after insertion
3 0 0 {0: [(0,3)]}
9 1 -1 {0: [(0,3)], -1: [(1,9)]}
20 1 1 {0: [(0,3)], -1: [(1,9)], 1: [(1,20)]}
15 2 0 {0: [(0,3),(2,15)], -1: [(1,9)], 1: [(1,20)]}
7 2 2 {0: [(0,3),(2,15)], -1: [(1,9)], 1: [(1,20)], 2: [(2,7)]}

Sorted columns:

col=-1: [9]
col=0: [(0,3),(2,15)] → [3,15]
col=1: [20]
col=2: [7]
Result: [[9],[3,15],[20],[7]]

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

Node Row Col Columns dict
Processed similarly, resulting in col=-2:[4], col=-1:[2], col=0:[1,5,6], col=1:[3], col=2:[7]
Sorted each column by row and value → [[4],[2],[1,5,6],[3],[7]]

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) BFS traversal takes O(N). Sorting