Leetcode # 314. Binary Tree Vertical Order Traversal

Problem

https://leetcode.com/problems/binary-tree-vertical-order-traversal

Solution: BFS

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    queue = collections.deque([(root, 0)]) if root else []
    nodes = defaultdict(list)
    while queue: 
      curr, pos = queue.popleft()
      # ... some process about target
      nodes[pos].append(curr.val)

      if curr.left:
        queue.append((curr.left,  pos - 1))
      if curr.right:
        queue.append((curr.right, pos + 1))
    
    return [nodes[key] for key in sorted(nodes.keys())]

Last Updated on 2025/08/04 by A1go