Is it possible to construct a binary tree. If preorder traversal of the binary tree and it's mirror tree both are given. If so how?
Preorder of binary tree - 1,2,4,5,6,3,7
Preorder of mirror of this tree - 1,3,7,2,5,6,4
Of course we can.
In your example, you know the root of the tree is 1. The problem then is to figure out of all remaining values, [2,4,5,6,3,7], which ones belong to left subtree and the ones on right subtree. You can then simply do a recursive call on both of these groups, and connect those subtrees with root.
Now imagine [2,4,5]forms the left subtree. So all values from right subtree, [6,3,7] must come before any of these values in mirror array. That's not the case here. So we must find a new point to split them up.
Now let [2,4,5,6] form left subtree. So, [3,7] must form right one. In mirror then, all of [3,7] must come before any of [2,4,5,6]. And that seems to be the case here.
To sum up, for every i from 0 to length of remaining values (all except 1), check if first i values in normal tree equals last i values in mirror and split if so, Since values might not maintain exact order, you might have to sort right before check, or put them in a set.