Domain 2MediumCORE

Binary Tree Vertical Order Traversal

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 root node 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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search

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 root node 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.

  1. Coordinate System: Let’s assign the root a column index of 0. Moving left decrements the index by 1, and moving right increments it by 1. This creates a coordinate system (row, col) where row is depth (implicitly handled) and col is horizontal distance.
  2. 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.
  3. Why BFS? Since a queue is FIFO, when we process depth d, all nodes at that depth are visited before any node at depth d+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.

  1. Initialization: If root is 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.
  2. Traversal: While the queue is not empty:
    • Pop the front element (current_node, current_col).
    • Append current_node.val to the list in our map at key current_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.
  3. 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: O(Nlog⁡N)O(N \log N) or effectively O(N)O(N). We visit each node exactly once (O(N)O(N)). Sorting the column indices at the end takes O(Wlog⁡W)O(W \log W), where WW is the number of distinct columns (at most N+1N+1). Given constraints and typical tree shapes, this dominates slightly but remains linear in practice.
  • Space Complexity: O(N)O(N). We store every node’s value once in our map (O(N)O(N)), 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 root at 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 val is handled correctly by Python’s list storage and integer comparison/sorting of column keys (which are integers).