Vertical Order Traversal of a Binary Tree

Problem Statement

Given a binary tree, return the vertical order traversal of its node values.

For each node located at coordinates (X, Y), its left child is positioned at (X-1, Y-1) and its right child at (X+1, Y-1).

Imagine drawing vertical lines from left to right across the tree. When a vertical line crosses nodes, list the node values from top to bottom (descending by Y coordinate).

If multiple nodes share the same coordinates, list the nodes with smaller values first.

Return a list of non-empty lists of values, ordered by the X coordinate from leftmost to rightmost.

Examples

Example 1:
Input: [5,3,22,null,null,17,9]
Output: [[3],[5,17],[22],[9]]
Explanation:
Assuming the root node 5 is at (0,0):
- Node 3 is at (-1,-1)
- Nodes 5 and 17 are at (0,0) and (0,-2)
- Node 22 is at (1,-1)
- Node 9 is at (2,-2)

Example 2:
Input: [10,6,15,2,7,12,20]
Output: [[2],[6],[10,7,12],[15],[20]]
Explanation:
Nodes 7 and 12 share the same position. Since 7 is smaller than 12, it appears first in the output list for that position.
    

Constraints

• The number of nodes in the tree is between 1 and 2000.
• Node values are integers ranging from 0 to 10,000.