The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
910 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.4k points)
edited by | 910 views

2 Answers

+24 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 $1$ is the only sorted list. hence it is the only possibility.
answered by Boss (11.4k points)
edited by
0
i have a doubt - Is this condition always follow .
+1
in order traversal will be always in sorted order
+4 votes

BST:

answered by Active (1.8k 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

35,487 questions
42,746 answers
121,458 comments
42,138 users