UGC NET CSE | November 2017 | Part 2 | Question: 25

Question

Post-order traversal of a given binary search tree $T$ produces following sequence of keys: $3,5,7,9,4,17,16,20,18,15,14$. Which one of the following sequences of keys can be the result of an in-order traversal of the tree $T$?

• A. $3,4,5,7,9,14,20,18,17,16,15$
• B. $20,18,17,16,15,14,3,4,5,7,9$
• C. $20,18,17,16,15,14,9,7,5,4,3$
• D. $3,4,5,7,9,14,15,16,17,18,20$

Answer 1

inorder traversal always gives sorted list in BST. therefore option D.

3,4,5,7,9,14,15,16,17,18,20

Answer 2

Option D

since given tree is BST

Inorder Traversal of BST is always key values of given nodes arranged in sorted ascending order.

Answer 3

Answer 4)

Inorder Traversal of BST is always a sorted (ascending) list.

Comments

Im unable to draw BST with given postorder

---

@ student2018 You can't draw BST directly from Postorder. You also need Inorder for that and that inorder is given in option 4.

P.S - Though to answer this question you need not draw BST.