Problem URL: Binary tree vertical order traversal

We will use BFS to traverse the tree. We will keep track of the horizontal distance of each node from the root. We will use a dictionary to store the nodes at each horizontal distance. We will use a queue to traverse the tree. We will use a set to keep track of the horizontal distances of the nodes. We will use a list to store the result.

# 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 []

        cols = collections.defaultdict(list)
        q = collections.deque([(root, 0)])
        while q:
            qLen = len(q)
            for _ in range(qLen):
                node, col = q.pop()
                cols[col].append(node.val)
                if node.left:
                    q.appendleft((node.left, col-1))
                if node.right:
                    q.appendleft((node.right, col+1))

        return [cols[i] for i in sorted(cols)]

Time complexity: O(n)
Space complexity: O(n)