LeetCode 314 - Binary Tree Vertical Order Traversal - 2024.03.09 solution

# 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]]:
        # handle the case where the input is empty
        if not root: return []

        # create some intermediate data structures / variables that will let us generate the answer
        level_order_traversal = []  # node and col_offset
        min_col_offset = 0
        max_col_offset = 0

        # populate the intermediate data structures / variables
        queue = [[root, 0]]
        while queue:
            current_node, col_offset = queue.pop(0)

            # update our intermediate data structures / variables
            level_order_traversal.append([current_node, col_offset])
            min_col_offset = min(min_col_offset, col_offset)
            max_col_offset = max(max_col_offset, col_offset)

            # add children to the queue
            if current_node.left:
                queue.append([current_node.left, col_offset - 1])
            if current_node.right:
                queue.append([current_node.right, col_offset + 1])

        # use the intermediate data structures/variables to generate the answer
        number_of_cols = max_col_offset - min_col_offset + 1
        output_list = [[] for _ in range(number_of_cols)]
        level_order_traversal.reverse()
        while level_order_traversal:
            current_node, offset = level_order_traversal.pop()
            column = offset - min_col_offset
            output_list[column].append(current_node.val)

        return output_list