Vertical Order Traversal

Given the root of a binary tree, calculate the **vertical order traversal**.

For each node at position (row, col):

- Root is at (0, 0).

- Left child of a node at (r, c) is at (r+1, c-1).

- Right child is at (r+1, c+1).

Return an array of node values grouped by column from left to right. Within the same column and row, sort by node value.

Input: root = [3,9,20,null,null,15,7]

Output: [[9],[3,15],[20],[7]]

Columns from left to right.

Input: root = [1,2,3,4,5,6,7]

Output: [[4],[2],[1,5,6],[3],[7]]

Nodes in same col+row are sorted.

Time

O(n log n)

sorting nodes.

Space

O(n)

#1 Standard case

Input: [3,9,20,null,null,15,7]

Expected: [[9],[3,15],[20],[7]]

#2 Full tree with ties

Input: [1,2,3,4,5,6,7]

Expected: [[4],[2],[1,5,6],[3],[7]]

#3 Single node

Input: [1]

Expected: [[1]]