Binary Tree Vertical Order Traversal

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Give every node a column: the root is in column 0, a left child is one column left of its parent (column − 1) and a right child one column right (column + 1). Implement vertical_order(root) -> list[list[int]] that returns the values column by column, from the leftmost column to the rightmost. Within a column, list the values from top to bottom. When two nodes share both a column and a depth, the one a left-to-right, level-by-level walk reaches first comes first (the one further left in the tree). An empty tree gives [].

#           6
#         /   \
#        2     7
#       / \   / \
#      1   5 4   9
#           \
#            3
vertical_order(root)   # [[1], [2], [6, 5, 4], [7, 3], [9]]

5 and 4 are both in column 0 and at depth 2. 5 hangs off the left subtree, so a level-by-level walk reaches it before 4. The 3 is 5's right child, so it lands in column 1, under 7.

vertical_order(from_list([1, 2, None, None, 3]))   # [[2], [1, 3]]: 3 is 2's right child
vertical_order(None)                               # []

• Up to 131,071 nodes; values are integers between -10^6 and 10^6 and may repeat.

⭐ Bonus: a speed test on a 131,071-node tree earns a star in O(n log n) or better.