Leaf Nodes from Preorder of BST

You are given a ‘root’ of a Binary Search Tree in preorder fashion, and your task is to print all the leaf nodes in the tree. A leaf node is a node whose left and right pointer point to NULL.

More formally, you have to print all the leaf nodes from left to right, i.e., they should be sorted.

Note:

A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

Example

For Example, the root node is given as follows :
‘ROOT’ = 6 4 3 -1 -1 5 -1 -1 8 7 -1 -1 9 -1 -1

Level 1 :
The root node of the tree is 6

Level 2 :
Left child of 6 = 4
Right child of 6 = 8

Level 3 :
Left child of 4 = 3
Right child of 4 = 5
Left child of 8 = 7
Right child of 8 = 9

Therefore all the leaf nodes are 3, 5, 7 and 9.

Input Format:

The first line of input contains a single integer ‘T,’ representing the number of test cases or queries to be run. 

The line of each test case contains elements in the pre-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.

Pre-order input refers to giving input in Node, left child, and then the right child and the recur for the same.

Output Format :

For every test case, print a single line that contains all the leaf nodes of the given Binary Search Tree.

The output of each test case is printed in a separate line.

Note:

You don’t have to print anything. It has already been taken care of. Just implement the function. 

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
0 <= data <= 10^3

Time Limit: 1 sec