Coding - Vertical Order Traversal of a Binary Tree

Here is the full interview question "Coding - Vertical Order Traversal of a Binary Tree" asked at Uber:

Problem Statement: Given the root of a binary tree, return the vertical order traversal of its nodes' values.

For each column i, you should return the nodes' values in this column from top to bottom, and for each column, the nodes' values should be from left to right.

Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Column -1: Only node with value 9 is in this column. Column 0: Nodes with values 3 and 15 are in this column. Column 1: Only node with value 20 is in this column. Column 2: Only node with value 7 is in this column.

Example 2: Input: root = [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: Column -2: Only node with value 4 is in this column. Column -1: Only node with value 2 is in this column. Column 0: Nodes with values 1, 5, and 6 are in this column. Column 1: Only node with value 3 is in this column. Column 2: Only node with value 7 is in this column.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 1000

Hints:

1. Use a map or dictionary to store the nodes' values for each column.
2. Perform a level-order traversal (BFS) to traverse the tree.
3. Keep track of the minimum and maximum column indices encountered during the traversal.

Solution: `python from collections import deque, defaultdict

class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def verticalOrder(root): if not root: return []

queue = deque([(root, 0)])
column_table = defaultdict(list)
min_col, max_col = 0, 0

while queue:
    node, col = queue.popleft()
    if node:
        column_table[col].append(node.val)
        min_col, max_col = min(min_col, col), max(max_col, col)
        queue.append((node.left, col - 1))
        queue.append((node.right, col + 1))

return [column_table[col] for col in range(min_col, max_col + 1)]

`

I found this problem on LeetCode (https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/) and provided the complete problem statement, examples, constraints, hints, and solution.