recategorized by
6,437 views
31 votes
31 votes
State whether the following statements are TRUE or FALSE:

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given?
recategorized by

5 Answers

Best answer
28 votes
28 votes

Yes it is possible since we can create Binary search tree , we know every Binary search tree is binary tree also  but there are many binary tree possible , so we know that there is many binary tree possible without inorder.

So, answer is NO for this question

Refer: http://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/

edited by
3 votes
3 votes
It is possible to create a bushy(complete) binary tree uniquely from only Preorder and Postorder

----NPTEL IIT DELHI Dr. Naveen Garg

 

But the question in about binary tree, not complete binary tree, so answer is NO.

Hope you learnt something today.
1 votes
1 votes

Unique Binary Tree is possible when, post-order/pre-order AND in-order traversals are given.
Unique Full Binary Tree is possible when, post-order AND pre-order traversals are given.
Unique Complete Binary Tree is possible when any ONE i.e, in-order or post-order or pre-order is given.

Therefore, for a Binary Tree, it is not possible to construct it uniquely when in-order isn’t given along with post-order/pre-order.

Answer:

Related questions

19 votes
19 votes
3 answers
1
makhdoom ghaya asked Nov 9, 2016
4,832 views
State whether the following statements are TRUE or FALSE:If the number of leaves in a tree is not a power of $2,$ then the tree is not a binary tree.
18 votes
18 votes
3 answers
2
makhdoom ghaya asked Nov 14, 2016
5,089 views
Construct a binary tree whose preorder traversal is$K\;L\;N\;M\;P\;R\;Q\;S\;T$and inorder traversal is$N\;L\;K\;P\;R\;M\;S\;Q\;T$
21 votes
21 votes
3 answers
3
makhdoom ghaya asked Nov 9, 2016
3,525 views
State whether the following statements are TRUE or FALSE:A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2...
14 votes
14 votes
2 answers
4
makhdoom ghaya asked Nov 9, 2016
3,882 views
State whether the following statements are TRUE or FALSE:The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.