We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Vertical Order Traversal

Number: 314

Difficulty: Medium

Paid? Yes

Companies: Meta, Bloomberg, Amazon, Google, DoorDash, Oracle, Microsoft, TikTok, Snap

Problem Description

Given the root of a binary tree, return the vertical order traversal of its nodes’ values. Nodes are grouped by their column (vertical) order where the leftmost column comes first and within the same column nodes are ordered from top to bottom. If two nodes share the same position (row and column), they should appear in the order from left to right.

Key Insights

  • Use Breadth-First Search (BFS) to traverse the tree level by level.
  • Track the column index for each node where root is column 0, left child is column-1, and right child is column+1.
  • Group nodes by their column indices using a hash table (or dictionary).
  • BFS traversal naturally handles left-to-right ordering within the same level.
  • Finally, sort the keys (column indices) to generate results from leftmost column to rightmost column.

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case due to sorting the column indices (n nodes in the worst-case if each node is on a unique column).
Space Complexity: O(n) for storing the node information and the resultant structure.

Solution

The solution uses BFS with a queue that stores nodes along with their corresponding column index. For each visited node, add its value to a dictionary keyed by its column index. When processing children, update the column index appropriately (left child: col-1, right child: col+1). After the traversal, sort the keys of the dictionary and compile the node values in order from smallest to largest column index. This approach guarantees that nodes at the same level will be processed in left-to-right order, matching the required output.

Code Solutions

from collections import deque, defaultdict

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

class Solution:
    def verticalOrder(self, root: TreeNode):
        # Return empty list if the tree is empty
        if not root:
            return []
        
        # Dictionary to hold nodes for each column index
        col_table = defaultdict(list)
        # Use deque for efficient FIFO queue for BFS; store tuple (node, column)
        queue = deque([(root, 0)])
        
        while queue:
            node, col = queue.popleft()
            # Append current node value to the list of its column
            col_table[col].append(node.val)
            # If there is a left child, assign column col-1
            if node.left:
                queue.append((node.left, col - 1))
            # If there is a right child, assign column col+1
            if node.right:
                queue.append((node.right, col + 1))
        
        # Extract the columns in sorted order to build the final result
        sorted_cols = sorted(col_table.keys())
        result = [col_table[col] for col in sorted_cols]
        return result
← Back to All Questions