Vertical Order Traversal Problem Statement

Given a binary tree, return the vertical order traversal of the values of the nodes in the tree.

In a vertical order traversal, for each node at position (X, Y), (X-1, Y-1) is the left child, and (X+1, Y-1) is the right child.

Imagine running a vertical line from X = -∞ to X = +∞. Whenever this line encounters nodes, add the node values in the order from top to bottom, sorted by decreasing Y coordinates.

Note:

If two nodes share the same position, the leftmost node's value is added first.

Example:

Input:

The tree structure: Level order input is 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

2 7 5 1 6 3 11 4 9

Explanation:

Given the binary tree:  The vertical order traversal is obtained.

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 3000 where N is the number of nodes
• 0 ≤ VAL ≤ 10^5 where VAL is a node's value
• Time Limit: 1 sec

Input:

An integer 'T' followed by T test cases. Each test case consists of a single line of space-separated values representing the level order traversal of the binary tree. Use -1 to denote null nodes.

Output:

For each test case, output the vertical order traversal, with node values separated by spaces. Each result should be on a new line.

Note:

Just implement the given function for the input. Printing is managed by the system.