The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
781 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 (69k points)
edited by | 781 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 Veteran (12.1k points)
edited by
i have a doubt - Is this condition always follow .
in order traversal will be always in sorted order
+4 votes

BST:

answered by Active (1.4k points)


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

33,593 questions
40,128 answers
114,021 comments
38,389 users