Binary Tree Vertical Order Traversal

lcpy gen -n 314   # by problem number
lcpy gen -s binary_tree_vertical_order_traversal   # by problem name

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
Output: [[4],[2,5],[1,10,9,6],[3],[11]]

from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n) — BFS visit plus one pass over the column span
    # Space: O(n) — queue and column buckets
    def vertical_order(self, root: TreeNode[int] | None) -> list[list[int]]:
        if root is None:
            return []

        columns: dict[int, list[int]] = {}
        queue: deque[tuple[TreeNode[int], int]] = deque([(root, 0)])
        min_col = max_col = 0
        while queue:
            node, col = queue.popleft()
            columns.setdefault(col, []).append(node.val)
            min_col = min(min_col, col)
            max_col = max(max_col, col)
            if node.left is not None:
                queue.append((node.left, col - 1))
            if node.right is not None:
                queue.append((node.right, col + 1))

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