All Root to Leaf Paths in Binary Tree

You have a binary tree containing 'N' nodes labeled from 1 to 'N'. Your objective is to enumerate every path from the root to each leaf.

A leaf is defined as a node with no child nodes.

Example:

Input

Given a binary tree:

Output

All the root to leaf paths are:
1 2 4
1 2 5
1 3

Input:

The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case holds an integer 'N', denoting the number of nodes in the tree.
The second line of each test case contains the node values of the tree in level order format ('-1' represents a NULL node).

Output:

For each test case, output all paths from root to leaf.

Example:

Consider the binary tree:

The input for the depicted tree:
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)

Constraints:

• 1 <= T <= 10²
• 1 <= N <= 3 * 10³

Note: You do not need to print anything. Implement the given function to solve the problem.