edited by
11,253 views
22 votes
22 votes

Postorder traversal of a given binary search tree, $T$ produces the following sequence of keys

$10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29$

Which one of the following sequences of keys can be the result of an in-order traversal of the tree $T$?

  1. $9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95$

  2. $9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29$

  3. $29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95$

  4. $95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29$

edited by

3 Answers

Best answer
37 votes
37 votes
In order traversal of $b$ binary search tree returns the element in sorted order - ascending (inorder is left parent then right. in a bst left is less than parent and right is greater than parent). In this option $A$ is the only sorted list. hence it is the only possibility.
0 votes
0 votes
Inorder traversal of a binary search tree is always a sorted sequence. So no need of pre and post order to find inorder of BST.
Answer:

Related questions

31 votes
31 votes
4 answers
1
Kathleen asked Sep 22, 2014
24,245 views
How many distinct binary search trees can be created out of $4$ distinct keys?$5$$14$$24$$42$
22 votes
22 votes
8 answers
3
Kathleen asked Sep 22, 2014
22,973 views
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:$nk$$(n-1)k + 1$$n(k-1) +1$$n(k-1)...
20 votes
20 votes
1 answer
4
Kathleen asked Sep 22, 2014
13,932 views
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ ar...