Vertical Order Traversal of a Binary Tree

Given a binary tree, your task is to return the vertical order traversal of its nodes' values.

For each node located at a position (X, Y), its left child will be at (X-1, Y-1) and its right child will be at (X+1, Y-1).

By drawing a vertical line from X = -infinity to X = +infinity, capture the node values touched by this line in order from top to bottom, respecting decreasing Y coordinates.

Note:

If two nodes have the same position, the node value that appears first will be the value on the left side.

Example:

Input:

For the depicted binary tree.

Output:

{2, 7, 5, 2, 6, 5, 11, 4, 9}

Input Format:

The first line contains an integer 'T', the number of test cases. Each test case contains elements in level order format. Values of nodes are separated by a single space, and -1 denotes a null node.

Example input for a tree:
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation:

Level 1 : Root node = 1
Level 2 : Left = 2, Right = 3
Level 3 : 2 -> Left = 4, Right = null (-1), 3 -> Left = 5, Right = 6
Level 4 : 4 -> Left = null (-1), Right = 7, 5, 6 -> all children null (-1)
Level 5 : 7 -> all children null (-1)

Note:

The above format is for understanding input formation. For the depicted tree, input will be:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format:

For each test case, print the vertical order traversal as single space-separated values. Each test case should be in a new line.

Note:

You do not need to print the results yourself; the function implementation is required only.

Constraints:

• 1 <= 'T' <= 100
• 0 <= 'N' <= 3000
• 0 <= 'VAL' <= 10^5, where 'VAL' is any node's value
• Time Limit: 1 sec