Binary Tree Vertical Order Traversal

Problem

Assign every node in a binary tree a column: the root is in column 0, a left child is one column to the left of its parent, and a right child is one column to the right. Return the node values grouped by column, columns ordered from leftmost to rightmost. Within a column, list nodes from top to bottom (shallower first); if two nodes share both a column and a depth, the one further left in the tree comes first. Return an empty list for an empty tree.

• The tree has at most 500 nodes and may be empty.
• Node values are integers between -200 and 200.

Examples

• root = [5, 6, 2, None, None, 9, 1] → [[6], [5, 9], [2], [1]]. Columns −1, 0, 1, 2; the 5 and the 9 share column 0 and the 5 is shallower.
• root = [5, 6, 4, 3, 8, 1, 9] → [[3], [6], [5, 8, 1], [4], [9]]. The 8 (right child of 6) and the 1 (left child of 4) both land in column 0 at the same depth; the 8 comes first because it is reached through the left subtree.
• root = [] → [].

Hints

1. Label each node with a column index as you traverse; what do the left and right children get?
2. Which traversal visits nodes in exactly the required within-column order (top to bottom, then left to right) without any extra sorting?
3. BFS carrying (node, column) pairs, appending each value to columns[column]; track the minimum and maximum column so the final assembly needs no sort.