Vertical Order Traversal of Binary Tree

You are given a binary tree having 'n' nodes.

Vertical order traversal is a traversal in which we traverse the nodes from left to right and then from top to bottom.

In the case of multiple nodes in the same place, we traverse them in the non-decreasing order of their value.

Formally, assume for any node at position (x, y), its left child will be at the position (x - 1, y + 1), and the right child at position (x + 1, y + 1). Assume the root is at coordinate (0, 0).

Run vertical lines from 'x' = -infinity to 'x' = +infinity. Now whenever this vertical line touches some nodes, we need to add those values of the nodes in order starting from top to bottom with the decreasing 'y' coordinates.

If multiple nodes have the same 'x' and 'y' coordinates, they will be accessed in non-decreasing order of values.

Find the vertical order traversal of the given tree.

Example :

Input: Let the binary tree be:

Output: [2, 7, 5, 2, 6, 5, 4, 11, 9]

Explanation: The nodes having the same 'x' coordinates are:

'x' = -2 : [2]
'x' = -1 : [7, 5]
'x' = 0 : [2, 6]
'x' = 1 : [5, 4, 11]
'x' = 2 : [9]

Here 4 and 11 have the same 'x' and 'y' coordinates. So they are considered in non-decreasing order.

Input Format:

The first line contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. So -1 would not be a part of the tree nodes.

Input format explanation:

The level order input for the tree depicted in the below image would be 

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level, and so on.
The input ends when all nodes at the last level are null (-1).

Output Format:

Print the vertical order traversal of the given binary tree.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.