Vertical Order Traversal of a Binary Tree

You are given a binary tree represented by its level order traversal. Some nodes might be missing and are represented by the keyword null. Your task is to perform a vertical order traversal on the tree.

The vertical order traversal is defined as follows: For each vertical column, nodes should be reported in order from top to bottom. For nodes at the same row, the order is determined by their order of appearance from left to right in the tree.

More formally, if we denote the horizontal distance (column) of the root as 0, then for any node at horizontal distance c, its left child has distance c-1 and its right child has distance c+1. The nodes in each column are sorted first by their depth (row) and then by the order in which they appear.

Input/Output Specifications:

The input is given as a single line from standard input containing node values separated by spaces. The value null indicates that a node does not exist at that position. The output should be printed to standard output as a list of lists (in Python-style list formatting) representing the vertical order traversal.

Example:

If the input is:

3 9 20 null null 15 7

Then the binary tree is constructed as:

\(\begin{array}{c} 3 \\ / \quad \backslash \\ 9 \quad\, 20 \\ \quad\, \backslash \quad\, / \\ \quad\, 15 \quad 7 \end{array}\)

And the output should be:

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

inputFormat

The input consists of a single line containing the level order traversal of the binary tree. The nodes are separated by spaces and missing nodes are represented by the string null. For example:

3 9 20 null null 15 7

outputFormat

The output should be printed as a single line representing a list of lists (using standard Python list notation) which contains the vertical order traversal of the binary tree.

For example:

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

## sample

3 9 20 null null 15 7

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