1.8k views

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$

in DS
edited | 1.8k views

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.
by Boss (11k points)
edited
0
i have a doubt - Is this condition always follow .
+1
in order traversal will be always in sorted order
+4
@rishi yadav this condition will be true in the case of binary search tree

BST:

by Active (2.8k points)