Vertical Order Traversal of a Binary Tree Interview Question for Meta

Given the root of a binary tree, calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the vertical order traversal of the binary tree.

For example, given the tree [3,9,20,null,null,15,7], the output should be [[9],[3,15],[20],[7]]. Also, given the tree [1,2,3,4,5,6,7], the output should be [[4],[2],[1,5,6],[3],[7]]. What is the time and space complexity of your proposed algorithm?

## Vertical Order Traversal of a Binary Tree

This problem asks us to perform a vertical order traversal of a binary tree. We need to traverse the tree and group the nodes based on their column index. Nodes in the same column should be sorted from top to bottom, and if they have the same row and column, they should be sorted by their values.

### 1. Brute Force Solution

A brute-force approach might involve traversing the tree and storing each node's value along with its row and column information. Then, we can sort the nodes based on the column index and row index. However, this approach might not be the most efficient.

### 2. Optimal Solution

A more efficient solution involves using a breadth-first search (BFS) approach along with a hash map to store nodes based on their column index. We can then sort the column indices and retrieve the nodes in the correct order.

```python
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)])  # Node, column

        while queue:
            node, column = queue.popleft()
            column_table[column].append(node.val)

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

        sorted_columns = sorted(column_table.keys())
        result = [column_table[col] for col in sorted_columns]

        return result

Example:

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

solution = Solution()
result = solution.verticalOrder(root)
print(result)  # Output: [[9], [3, 15], [20], [7]]

3. Big(O) Run-time Analysis

Time Complexity: O(N log W), where N is the number of nodes in the binary tree and W is the width (number of unique columns) of the binary tree. The BFS traversal takes O(N) time. Sorting the columns takes O(W log W) time. In the worst case, W can be equal to N, so the time complexity is O(N log N).

4. Big(O) Space Usage Analysis

Space Complexity: O(N), where N is the number of nodes in the binary tree. This is because, in the worst-case scenario (a skewed tree), the queue might contain all the nodes of the tree at some point. Also, the column_table hash map will store the nodes, which could potentially be all nodes in the tree.

5. Edge Cases

Empty Tree: If the root is None, return an empty list.
Skewed Tree: The algorithm should handle left-skewed and right-skewed trees correctly.
Duplicate Values: If multiple nodes have the same value and are in the same row and column, the algorithm should maintain the correct order (though the problem statement doesn't specify behavior for this case, the solution implicitly handles it due to the nature of BFS).
Large Tree: Ensure the code is efficient enough to handle trees with up to 1000 nodes.