The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.2k 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$

asked in DS by Veteran (59.6k points)
edited by | 1.2k views

2 Answers

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

BST:

answered by Active (2k points)
Answer:


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,855 questions
47,520 answers
145,893 comments
62,278 users