The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.5k views

The preorder traversal sequence of a binary search tree is $30, 20, 10, 15, 25, 23, 39, 35, 42$. Which one of the following is the postorder traversal sequence of the same tree?

  1. $10, 20, 15, 23, 25, 35, 42, 39, 30$
  2. $15, 10, 25, 23, 20, 42, 35, 39, 30$
  3. $15, 20, 10, 23, 25, 42, 35, 39, 30$
  4. $15, 10, 23, 25, 20, 35, 42, 39, 30$
asked in DS by Veteran (359k points)
edited by | 1.5k views

2 Answers

+26 votes
Best answer

Since it is a binary search tree, its inorder traversal produces a sorted sequence i.e. $\text{10, 15, 20, 23, 25, 30, 35, 39, 42}$.

Now given inorder and preorder traversals, we get following tree :

From this, we can give postorder traversal sequence as $\text{15,10,23,25,20,35,42,39,30}$ i.e. option (D).

answered by Boss (11.3k points)
edited by
0
30 we came to know is the root of the tree . how did u come to know root of left subtree ?
+1

check the pre order  30, 20, 10, 15, 25, 23, 39, 35, 42.So 20 will next and followed in same way.

+1
acha got it
0 votes

takes time but there will no confusion

answered by (95 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

41,078 questions
47,675 answers
147,465 comments
62,393 users