You are given an Inorder Traversal sequence.
Find all possible Binary Trees with the given Inorder traversal and print their preorder traversals.
Below are all possible different binary trees with the same inorder {1, 2, 3}:
1 1 2 3 3 \ \ / \ / / 2 3 1 3 1 2 \ / \ / 3 2 2 1
Only an integer N, 1 <= N <= 10, giving that the inorder traversal sequence is {1, 2, 3, ..., N}.
Output all the possible preorder traversals in lexicographical order.
Remember to add a new line in the end.