# 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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        q = deque([(root, 0)])
        data = {}
        min_column, max_column = 0, 0
        current_row = 0
        while q:
            current_row += 1
            for _ in range(len(q)):
                node, column = q.popleft()
                min_column, max_column = min(min_column, column), max(max_column, column)
                
                if column not in data:
                    data[column] = defaultdict(list)
                data[column][current_row].append(node.val)
                if node.left:
                    q.append((node.left, column - 1))
                if node.right:
                    q.append((node.right, column + 1))
        #print(data)
        for i in range(min_column, max_column + 1):
            new_row = []
            for row in data[i].values():
                new_row.extend(sorted(row))
            result.append(new_row)
        return result