Diagonal Traversal of a Binary Tree

Given a binary tree of integers, find its diagonal traversal. Refer to the example for clarification on diagonal traversal.

Example:

Explanation:

Consider lines at an angle of 135 degrees (with respect to the standard X-axis) in between nodes. All nodes between two consecutive lines belong to the same diagonal.

Output:

The diagonal traversal for the above tree is: 0 2 6 1 5 3 4 7

Input:

The first line contains an integer 'T' which denotes the number of test cases.
The only line of each test case contains elements in the level order form. Values of nodes are separated by a single space. Use -1 in place of null nodes. -1 is not a tree node value.

Example:

The input for the tree depicted in the above image will be: 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)

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

Output:

For each test case, return the diagonal traversal of the binary tree, separated by a single space.

Constraints:

• 1 <= T <= 100
• 0 <= N <= 3000
• 0 <= data <= 10⁵ and data != -1
• Where ‘N’ is the total number of nodes in the binary tree, and 'data' is the value of the binary tree node
• Time limit: 1 sec

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.