The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
209 views

someone please explain this question 

A binary search tree contains the values 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

 

 

how the option D is correct?

A

53124786

B

53126487

C

53241678

D 53124768
in Study Resources by (41 points) | 209 views

2 Answers

0 votes
Best answer
  • We know the inorder of BST is sorted. So inorder is 1,2,3,4,5,6,7,8 

  • And preorder is given in option . With the help of inorder and preorder we construct a unique tree .

  • After constructing tree check it preorder is right or not .

  •  

 

by Boss (34.6k points)
edited by
0
pre order means .. parent left right .. so for this 5 3 1 2 4 7 86

 

you create tree like this  5 then 3 then on right side 7 ? why

 

where as pre order (parent left right )

it become 5 ,3 then on right side 1 ? why 7 ?
0

I think you are canfused how to create binary tree is preorder and inorder is given .

Look at the following steps

+1

 

for OPTION A why not we create tree just like 2nd image .. where as you created 2nd image for option D 

0

@abhishekmehta4u  please responce

+1
Amber you are right . I am doing silly mistakes. Now i am updationg soln
+1
great
0
tree image would be like 2nd image only amber in option A but preorder sequence is wrong.!

and the first tree which you have made in your picture is not BST...so its wrong...6 should be on left to 7..
+1 vote

D is coorect  preorder traversal as you are given bst the inorder will be sorted i.e it will be 1,2,3,4,5,6,7,8

now when you take D option than tree which is traversed for preorder will be 

 

by Active (3.9k points)
edited by

Related questions

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
50,093 questions
55,328 answers
190,852 comments
86,255 users