How do you solve Vertical Order Traversal of a Binary Tree on LeetCode?

Vertical Order Traversal of a Binary Tree (LeetCode #987) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using BFS allows us to capture the vertical order naturally as we traverse level by level.

What is the time complexity of Vertical Order Traversal of a Binary Tree?

The optimal solution for Vertical Order Traversal of a Binary Tree runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to the sorting of the nodes within each column, where n is the number of nodes. The BFS traversal itself is O(n).

What is the brute force solution for Vertical Order Traversal of a Binary Tree?

The brute force approach for Vertical Order Traversal of a Binary Tree is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute force approach, we can traverse the tree and store each node's value along with its column index. After collecting all nodes, we can sort them based on their column and row indices to get the vertical order. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Vertical Order Traversal of a Binary Tree?

Clearly explain your thought process and how you plan to traverse the tree. Discuss edge cases, such as empty trees or trees with only one node. Be prepared to optimize your solution after presenting the brute force approach.

What are common mistakes when solving Vertical Order Traversal of a Binary Tree?

Forgetting to handle nodes that share the same row and column correctly during sorting. Not using a data structure that allows for easy grouping of nodes by their column index.

#987

Vertical Order Traversal of a Binary Tree

Hard

Hash TableTreeDepth-First SearchBreadth-First SearchSortingBinary TreeHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(n)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a breadth-first search (BFS) to traverse the tree while keeping track of the column indices. This allows us to directly collect nodes in the correct order without needing to sort them afterward.

⚙️

Algorithm

3 steps

1Step 1: Use a queue to perform BFS, storing each node along with its row and column indices.
2Step 2: Use a hashmap to group nodes by their column index.
3Step 3: Sort the nodes in each column by their row index and value, then compile the results.

solution.py27 lines

1# Full working Python code
2from collections import defaultdict, deque
3class TreeNode:
4    def __init__(self, val=0, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9def verticalTraversal(root):
10    if not root:
11        return []
12    column_table = defaultdict(list)
13    queue = deque([(root, 0, 0)])  # (node, row, column)
14    while queue:
15        node, row, col = queue.popleft()
16        column_table[col].append((row, node.val))
17        if node.left:
18            queue.append((node.left, row + 1, col - 1))
19        if node.right:
20            queue.append((node.right, row + 1, col + 1))
21    sorted_columns = sorted(column_table.keys())
22    result = []
23    for col in sorted_columns:
24        # Sort by row first, then by value
25        column_table[col].sort()
26        result.append([val for row, val in column_table[col]])
27    return result

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting of the nodes within each column, where n is the number of nodes. The BFS traversal itself is O(n).

1Using BFS allows us to capture the vertical order naturally as we traverse level by level.
2Sorting nodes by row and value ensures that we maintain the correct order when nodes share the same column.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.