Leetcode 314 — Facebook Interview Question

# 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

'''
        3(0)
       /    \
     9(-1)   20(1)
    / \      /     \
 null null 15(0)   7(2)
'''
from collections import deque, defaultdict
class Solution:
  def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
      return []
    res = []
    # for every item in the q, it will be (node, col)
    q = deque()
    q.append((root, 0))
    col_map = defaultdict(list)

    # BFS travelling through the tree
    while q:
      node, col = q.popleft()
      col_map[col].append(node.val)

      if node.left:
        left_col = col - 1
        q.append((node.left, left_col))

      if node.right:
        right_col = col + 1
        q.append((node.right, right_col))

    cols = col_map.keys()
    min_col = min(cols)
    max_col = max(cols)

    for c in range(min_col, max_col+1):
      if col_map[c]:
        res.append(col_map[c])
    return res