314. Binary Tree Vertical Order Traversal

This can be done easiest by bfsing through each level, since it goes level by level for you automatically. This keeps everything in order.

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        levels = defaultdict(list)
        q = deque([(root, 0)])
        start = 0
        end = 0
        while q:
            node, col = q.popleft()
            if not node:
                continue
            levels[col].append(node.val)
            start = min(start, col)
            end = max(end, col)
            q.append((node.left, col - 1))
            q.append((node.right, col + 1))
        
        return [levels[n] for n in range(start, end + 1)]