NIELIT 2018-80

Question

_____  traversals are not sufficient to build a binary tree.

• A. Preorder and Inorder
• B. Postorder and Inorder
• C. Postorder and Preorder
• D. None of these

Comments

C. post order  and pre order.

Answer 1

TO CONSTRUCT A BINARY TREE INORDER TRAVERSAL IS A PREREQUISITE.

so OPTION C is correct.

 

refer:-> https://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/

Answer 2

C is correct. 

We can't build a tree without the in-order traversal. Why?

This is so because we cannot separate the left sub-tree and right sub-tree using the pre-order or post-order traversal alone.

Even if we have all three i.e. Prorder, Postorder and Level Order we cannot get unique tree.

Ref: https://stackoverflow.com/questions/33062228/why-it-is-impossible-to-construct-binary-tree-with-pre-order-post-order-and-lev

 

Answer 3

We can't build a tree without the in-order traversal.
Consider two different trees,
TREE-1
root=a;
root→ left=b;
root→ left→ right=c;
TREE-2
root=a;
root→ right=b;
root→ right→ left=c;
Both the trees are different, but have same pre-order and post-order sequence.
pre-order - a b c
post-order - c b a
Because we cannot separate the left subtree and right subtree using the pre-order or post-order traversal alone