Vertical Order Traversal of a Binary Tree

Given a binary tree, perform a vertical order traversal of its nodes. The tree is provided in level-order as space-separated tokens where null indicates a missing node. Each node is assigned a coordinate \((x, y)\) where the root is at \((0,0)\), the left child of a node at \((x,y)\) is at \((x-1, y+1)\), and the right child is at \((x+1, y+1)\).

Nodes are grouped by their vertical columns (i.e. by their x-coordinate). Within the same column, nodes are ordered first by their row (y-coordinate) and if they share the same row, they are listed from left to right.

The output should be a list of lists, where each inner list contains the node values in one vertical column, starting from the leftmost column.

inputFormat

The input is a single line containing space-separated tokens representing the level-order traversal of the binary tree. Each token is either an integer or the string null indicating the absence of a node.

For example: 3 9 20 null null 15 7

outputFormat

Output the vertical order traversal as a list of lists in JSON format. For example, for the input above, the output should be: [[9],[3,15],[20],[7]].

3 9 20 null null 15 7

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