Give you a in-order traversal of a binary Tree. Please find the minimum pre-order traversal of the tree.
We compare pre-order by their alphabet order. For example:
If two pre-order are: {6, 4, 2, 3, 1, 5}, {6, 1, 2, 3, 5, 4},
Since 6 = 6, 4 > 1, the second one is smaller.
First line is an integer T, which is the number of test cases. (1 <= T <= 10)
For each test case, there will be an integer in a single line N (1 <= N <= 50000). N is the number of nodes. The nodes are numbered from 1 to N.
Then there will be one line. Which is the in-order traversal of the Tree.
1
8
3 2 4 1 6 5 7 8
1 2 3 4 5 6 7 8
Bonus problem.