Given Preorder and In-order, We get Unique (One) binary tree. Why??
Because What do we require to construct a unique Binary tree? Two things I'd say. "Root and What's on its left and What's on its right" on every level. So, Pre-order keeps on giving you root when scanned from left to right and In-order keeps giving you information of "What's on its left and What's on its right". Hence, We get a Unique Binary Tree.
Build yourself a small example tree of about 6 or 7 nodes and see what happens.
Consider the example where the root has value A. In the preorder traversal, that A is printed first. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
We can apply this concept recursively to reconstruct the left subtree and the right subtree.
Is it possible that inorder and preorder is given and no such tree (binary) is possible that satisfies both?
No. If In-order and Pre-order of a Binary tree are given then of course we will get at least and at most one Binary tree.
See, I get your doubt.
Say, I give you..
Pre-order = 1,4,3,2
In-order = 3,2,1,4
You won't get any Binary tree which satisfies both the above Orders. But the Thing we did wrong here is that We named these Two Random Orders (Two Permutations you can say) as "Preorder and Inorder".
We should not have said these Orders/Permutations as Pre-order and In-order in the first place if they do not belong to any binary tree at all. When You say that Pre-order and In-order are given, You mean that For Some (At least One) Binary tree these Orders are given. It's the name/Term that matters here (No offense Shakespeare)
Note that To the Algorithm, We can provide such Random Orders.
