314. Binary Tree Vertical Order Traversal
Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 47.3%
Problem Breakdown
We need to traverse a binary tree and group its values into vertical columns based on their horizontal distance from the root’s central axis.
- Input: A
rootnode of a binary tree (can be empty). - Output: A list of lists where each inner list represents one column, ordered from leftmost to rightmost. Within each column, nodes appear in top-to-bottom order based on their depth; if multiple nodes share the same row and column index, they are ordered by insertion sequence (left-to-right within that level).
- Key Constraint: We must handle empty trees gracefully. The values can be negative or zero, which doesn’t affect logic but requires standard integer handling.
Intuition
To solve this efficiently, we need to track the horizontal position of every node relative to the root.
- Coordinate System: Let’s assign the root a column index of
0. Moving left decrements the index by1, and moving right increments it by1. This creates a coordinate system(row, col)where row is depth (implicitly handled) and col is horizontal distance. - Traversal Strategy: A Depth-First Search (DFS) would visit nodes in an arbitrary order relative to columns unless we explicitly track levels or sort results later. However, Breadth-First Search (BFS) naturally processes the tree level-by-level.
- Why BFS? Since a queue is FIFO, when we process depth
d, all nodes at that depth are visited before any node at depthd+1. This guarantees “top-to-bottom” ordering within columns automatically. Furthermore, because we enqueue left children before right children of the same parent (or parents in order), the relative horizontal position for nodes at the same row is preserved naturally without needing explicit sorting during traversal.
Approach
We will use a standard BFS approach with a queue to maintain processing order and a hash map to group values by column index.
- Initialization: If
rootis empty, return an empty list immediately. Initialize a deque for the queue storing tuples of(node, col_index). Start with(root, 0). Use a dictionary (defaultdict(list)) where keys are column indices and values are lists to store node values. - Traversal: While the queue is not empty:
- Pop the front element
(current_node, current_col). - Append
current_node.valto the list in our map at keycurrent_col. - If a left child exists, push it with index
current_col - 1. - If a right child exists, push it with index
current_col + 1.
- Pop the front element
- Result Construction: After traversal, extract all column indices from the dictionary keys and sort them in ascending order to ensure we return columns left-to-right. Construct the final list of lists using these sorted keys.
Complexity Analysis
- Time Complexity: or effectively . We visit each node exactly once (). Sorting the column indices at the end takes , where is the number of distinct columns (at most ). Given constraints and typical tree shapes, this dominates slightly but remains linear in practice.
- Space Complexity: . We store every node’s value once in our map (), plus space for the queue which holds at most one level of nodes (bounded by width or height depending on shape).
Solution
from collections import deque, defaultdict
from typing import Optional, List
# 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
def verticalOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
# Queue stores (node, column_index)
queue = deque([(root, 0)])
col_map = defaultdict(list)
while queue:
node, col = queue.popleft()
# Append value to the current column's list
col_map[col].append(node.val)
if node.left:
queue.append((node.left, col - 1))
if node.right:
queue.append((node.right, col + 1))
# Sort columns by index (left to right) and return values
sorted_cols = []
for key in sorted(col_map.keys()):
sorted_cols.append(col_map[key])
return sorted_cols
Edge Cases Handled
- Empty Tree: The function checks
if not rootat the start and returns an empty list immediately. - Single Node: Queue processes one node, map has key 0 with one value; sorting keys yields a single-element result.
- Negative Values: Since we store values directly in lists without using them as indices or logic gates for traversal order, negative
valis handled correctly by Python’s list storage and integer comparison/sorting of column keys (which are integers).