LeetCode 314 - Binary Tree Vertical Order Traversal

The problem asks us to group the nodes of a binary tree by their vertical columns and return those groups from left to right.

leetcodemediumhash-tabletreedepth-first-searchbreadth-first-searchsortingbinary-tree

LeetCode Problem 314

Difficulty: 🟡 Medium
Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Sorting, Binary Tree

Solution

Problem Understanding

The problem asks us to group the nodes of a binary tree by their vertical columns and return those groups from left to right.

Each node in the tree belongs to a conceptual coordinate system:

  • The root starts at column 0
  • Moving to the left child decreases the column index by 1
  • Moving to the right child increases the column index by 1

The output should contain all nodes that belong to the same column grouped together. The columns themselves must appear from the leftmost column to the rightmost column.

Within a single column, nodes must appear from top to bottom. This requirement is important because it determines the traversal strategy we should use. Additionally, if two nodes share both the same row and the same column, they must appear from left to right.

The input is the root node of a binary tree. The tree may contain up to 100 nodes, which is relatively small, but the ordering requirements are strict enough that a careless traversal can still produce incorrect results.

For example, consider this tree:

        3
       / \
      9   20
         /  \
        15   7

The column assignments are:

Column -1: 9
Column  0: 3, 15
Column  1: 20
Column  2: 7

So the result becomes:

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

An important detail is the tie-breaking rule. If two nodes share the same row and column, the node encountered first from left to right must appear first in the output. This requirement strongly suggests using Breadth-First Search instead of a naive Depth-First Search.

Several edge cases are important:

  • An empty tree should return an empty list
  • A tree with only one node should return a single column
  • Multiple nodes may fall into the same column
  • Nodes at the same row and column must preserve left-to-right ordering
  • Highly skewed trees can create many negative or positive column indices

The problem guarantees that the input is a valid binary tree and that node values are within a small integer range.

Approaches

Brute Force Approach

A brute-force solution would first assign coordinates (row, column) to every node using a traversal such as DFS. After collecting all nodes, we could sort them globally by:

  1. Column
  2. Row
  3. Left-to-right visitation order

Finally, we would group nodes by column.

This works because sorting explicitly enforces the required ordering rules. However, the approach introduces unnecessary overhead. We must store extra metadata for every node and perform a sort operation over all collected entries.

Although the constraint size is only 100, the approach is less elegant and does not naturally model the traversal ordering requirement.

Key Insight for the Optimal Solution

The key observation is that Breadth-First Search naturally processes nodes level by level, which already guarantees top-to-bottom ordering.

Even better, when BFS processes nodes from left to right within each level, it automatically preserves the required tie-breaking rule for nodes that share the same row and column.

This means we do not need to explicitly store row indices or perform complicated sorting. We only need:

  • A queue for BFS traversal
  • A hash map from column index to node values
  • Tracking of the minimum and maximum column indices encountered

As we traverse:

  • Left child gets column col - 1
  • Right child gets column col + 1

Because BFS already guarantees correct visitation order, appending values directly into each column list produces the correct result.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Collects coordinates and sorts all nodes
Optimal O(n) O(n) BFS naturally preserves required ordering

Algorithm Walkthrough

  1. Start by handling the empty tree case.

If the root is None, there are no nodes to process, so return an empty list immediately. 2. Initialize a queue for Breadth-First Search.

Each queue entry stores:

  • The current node
  • Its column index

The root begins at column 0. 3. Create a hash map that maps column indices to lists of node values.

This allows us to efficiently append nodes into their vertical groups as we traverse the tree. 4. Track the smallest and largest column indices encountered.

Since column indices can become negative or positive, we need these boundaries later to output columns from left to right in order. 5. Perform BFS traversal.

Repeatedly remove nodes from the queue:

  • Append the node value into the list for its column
  • Update the minimum and maximum column indices
  • Add the left child with column col - 1
  • Add the right child with column col + 1
  1. Construct the final answer.

Iterate from the minimum column index to the maximum column index and collect the corresponding lists from the hash map. 7. Return the completed vertical order traversal.

Why it works

The algorithm works because BFS processes nodes level by level, which guarantees top-to-bottom ordering. Within the same level, nodes are visited from left to right because the left child is enqueued before the right child. Therefore, nodes sharing the same row and column automatically appear in the required order. Grouping nodes by column during traversal directly constructs the correct vertical ordering.

Python Solution

from collections import defaultdict, deque
from typing import List, Optional

# 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        column_table = defaultdict(list)
        queue = deque([(root, 0)])

        min_column = 0
        max_column = 0

        while queue:
            node, column = queue.popleft()

            column_table[column].append(node.val)

            min_column = min(min_column, column)
            max_column = max(max_column, column)

            if node.left:
                queue.append((node.left, column - 1))

            if node.right:
                queue.append((node.right, column + 1))

        result = []

        for column in range(min_column, max_column + 1):
            result.append(column_table[column])

        return result

The implementation begins with an early return for the empty tree case.

A defaultdict(list) is used to store the nodes belonging to each vertical column. This avoids manual existence checks before appending values.

The queue stores pairs of (node, column) so that every node knows its current vertical position.

During BFS traversal:

  • The current node value is appended into its column list
  • Column boundaries are updated
  • Children are inserted into the queue with adjusted column indices

Finally, the algorithm iterates from the smallest column index to the largest one, ensuring the output columns appear from left to right.

The implementation relies on BFS ordering to satisfy both:

  • Top-to-bottom ordering
  • Left-to-right tie-breaking

No explicit sorting is needed.

Go Solution

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

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

    type Pair struct {
        node   *TreeNode
        column int
    }

    columnTable := make(map[int][]int)
    queue := []Pair{{root, 0}}

    minColumn := 0
    maxColumn := 0

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        node := current.node
        column := current.column

        columnTable[column] = append(columnTable[column], node.Val)

        if column < minColumn {
            minColumn = column
        }

        if column > maxColumn {
            maxColumn = column
        }

        if node.Left != nil {
            queue = append(queue, Pair{node.Left, column - 1})
        }

        if node.Right != nil {
            queue = append(queue, Pair{node.Right, column + 1})
        }
    }

    result := [][]int{}

    for column := minColumn; column <= maxColumn; column++ {
        result = append(result, columnTable[column])
    }

    return result
}

The Go implementation follows the same logic as the Python version but uses Go-specific data structures.

A custom Pair struct stores both the node pointer and its column index. The queue is implemented using a slice, where elements are removed from the front.

The hash map uses map[int][]int to associate column indices with node values.

Unlike Python, Go requires explicit nil checks and manual queue management. Otherwise, the overall algorithm remains identical.

Worked Examples

Example 1

Input:

    3
   / \
  9   20
     /  \
    15   7

BFS Traversal State

Step Queue Current Node Column Column Table
1 [(3,0)] 3 0 {0:[3]}
2 [(9,-1),(20,1)] 9 -1 {0:[3], -1:[9]}
3 [(20,1)] 20 1 {0:[3], -1:[9], 1:[20]}
4 [(15,0),(7,2)] 15 0 {0:[3,15], -1:[9], 1:[20]}
5 [(7,2)] 7 2 {0:[3,15], -1:[9], 1:[20], 2:[7]}

Final result:

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

Example 2

Input:

        3
       / \
      9   8
     / \ / \
    4  0 1  7

BFS Traversal State

Step Current Node Column Column Table
1 3 0 {0:[3]}
2 9 -1 {0:[3], -1:[9]}
3 8 1 {0:[3], -1:[9], 1:[8]}
4 4 -2 {-2:[4], -1:[9], 0:[3], 1:[8]}
5 0 0 {-2:[4], -1:[9], 0:[3,0], 1:[8]}
6 1 0 {-2:[4], -1:[9], 0:[3,0,1], 1:[8]}
7 7 2 {-2:[4], -1:[9], 0:[3,0,1], 1:[8], 2:[7]}

Final result:

[[4], [9], [3,0,1], [8], [7]]

Example 3

Input:

           1
         /   \
        2     3
       / \   / \
      4  10 9  11
       \
        5
         \
          6

Important Observation

Nodes 10, 9, and 6 all end up in column 0.

BFS ordering processes them in this order:

1 -> 10 -> 9 -> 6

So the final middle column becomes:

[1,10,9,6]

This demonstrates why BFS is critical. A DFS traversal could easily produce the wrong ordering.

Final result:

[[4], [2,5], [1,10,9,6], [3], [11]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once
Space O(n) Queue and hash map can store all nodes

The BFS traversal processes every node exactly one time, so the runtime is linear in the number of nodes.

The auxiliary space comes from two structures:

  • The queue used for BFS
  • The hash map storing vertical columns

In the worst case, both may contain up to n nodes.

Test Cases

from collections import deque
from typing import Optional

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

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]):
        from collections import defaultdict, deque

        if not root:
            return []

        column_table = defaultdict(list)
        queue = deque([(root, 0)])

        min_column = 0
        max_column = 0

        while queue:
            node, column = queue.popleft()

            column_table[column].append(node.val)

            min_column = min(min_column, column)
            max_column = max(max_column, column)

            if node.left:
                queue.append((node.left, column - 1))

            if node.right:
                queue.append((node.right, column + 1))

        return [
            column_table[c]
            for c in range(min_column, max_column + 1)
        ]

s = Solution()

# Example 1
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

assert s.verticalOrder(root) == [[9], [3, 15], [20], [7]]  # basic example

# Example 2
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(8)
root.left.left = TreeNode(4)
root.left.right = TreeNode(0)
root.right.left = TreeNode(1)
root.right.right = TreeNode(7)

assert s.verticalOrder(root) == [[4], [9], [3, 0, 1], [8], [7]]  # multiple same-column nodes

# Example 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(10)
root.right.left = TreeNode(9)
root.right.right = TreeNode(11)
root.left.left.right = TreeNode(5)
root.left.left.right.right = TreeNode(6)

assert s.verticalOrder(root) == [[4], [2, 5], [1, 10, 9, 6], [3], [11]]  # BFS ordering

# Empty tree
assert s.verticalOrder(None) == []  # no nodes

# Single node
root = TreeNode(1)

assert s.verticalOrder(root) == [[1]]  # single-column tree

# Left-skewed tree
root = TreeNode(1)
root.left = TreeNode(2)
root.left.left = TreeNode(3)

assert s.verticalOrder(root) == [[3], [2], [1]]  # negative columns only

# Right-skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)

assert s.verticalOrder(root) == [[1], [2], [3]]  # positive columns only

# Same row and same column ordering
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(5)

assert s.verticalOrder(root) == [[2], [1, 4, 5], [3]]  # left-to-right tie breaking

Test Summary

Test Why
Empty tree Validates handling of None input
Single node Confirms simplest valid tree
Left-skewed tree Tests negative column handling
Right-skewed tree Tests positive column handling
Multiple nodes in same column Verifies grouping correctness
Same row and same column Verifies BFS left-to-right ordering
Deep irregular tree Tests traversal robustness

Edge Cases

Empty Tree

An empty tree is one of the most common failure points. If the implementation assumes the root always exists, accessing child pointers or node values will raise errors. The solution handles this immediately with:

if not root:
    return []

This guarantees safe execution for the smallest possible input.

Nodes Sharing the Same Row and Column

This is the trickiest logical edge case in the problem. Consider:

      1
     / \
    2   3
     \ /
      4 5

Both 4 and 5 occupy the same row and column. The correct ordering is [4, 5] because 4 appears first from left to right.

A DFS implementation can accidentally produce [5, 4] depending on traversal order. BFS avoids this issue because nodes are processed level by level and children are enqueued left before right.

Highly Skewed Trees

A tree that only extends leftward or rightward creates continuously decreasing or increasing column indices.

For example:

    1
   /
  2
 /
3

The columns become 0, -1, and -2.

If the implementation does not track minimum and maximum column indices correctly, the final output ordering may be incorrect or incomplete. The solution explicitly maintains both boundaries during traversal, ensuring all columns are returned in proper left-to-right order.