Binary Tree

Question

$\text{Given preorder and inorder, how many binary trees are possible?}$

Comments

One only since if you try to change the structure of Binary tree it will change one of the order either preorder or postorder . Take 2-3 example and observe this.

---

Is it possible that inorder and preorder is given and no such tree (binary) is possible that satisfies both?

---

no

Answer 1

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.

Comments

Thanks a lot...

Answer 2

• Inorder,preorder-->unique binary tree

• Inorder,postorder-->unique binary tree

• Preorder,postorder---->we can not construct unique binary tree.

Comments

Is it possible that inorder and preorder is given and no such tree (binary) is possible that satisfies both?

---

We can get unique binary tree.

---

Sir, suppose preorder is ABC, inorder is CAB, then I think no such tree is possible.So may i conclude that if inorder and preorder/postorder is given then we get unique binary tree or 0(none) binary tree. If preorder and postorder is given we may get 0 or unique or many binary trees.