+22 votes
4.4k views

A binary search tree contains the value $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?

1. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 8 \ 6$
2. $5 \ 3 \ 1 \ 2 \ 6 \ 4 \ 8 \ 7$
3. $5 \ 3 \ 2 \ 4 \ 1 \ 6 \ 7 \ 8$
4. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 6 \ 8$
asked in DS
edited | 4.4k views
+1
Note here in all options 5 is the first one traversed hence it is root. So we have now two sets of vertices { 1,2 3, 4} on left subtree and {6, 7, 8 } on right subtree.

Proceed in this way using option elimination you will get D as valid answer.

## 4 Answers

+27 votes
Best answer

Note: PreOrder means Root-Left-Right Traversal of tree.

By Option Elimination:-

B. False. Because $5$ is root so in preorder sequence first $5$ elements must contain $1$ to $5$ But $6$ comes here. So false.

So, now common things in option A,C,D is $5,3$ means $5$ root then LHS subtree root is $3$ . now $3$ s LHS is $1,2$ so they should come first rather than $4$. So option C is False.

Now Check for Option A,D.

Root $5$'s RHS is $6,7,8$ now as per Option A,D $7$ is Root so $6$ should be Left and $8$ should be Right so pre order for Right sub tree is $7,6,8$ (Root-L-R). This satisfies option D.

answered by Boss (23.2k points)
edited
0
@bikram

hi

thanks for all answers
0

@Rajesh Pradhan Thank You so much for explaining such nice approach.

0

I'm able to make tree for option (b) also. Please guide me where am I heading wrong!

0
@janeb

What you're saying is correct. But I'm thinking if the option (b) is wrong then how am I able to make tree. What mistake did I make while making tree?
0
@janeb. Got your point. Thanks for putting so much effort.
0
solution is not productive, any other solution please.
+13 votes

Answer: D

The tree is:

answered by Boss (34.1k points)
0

can  u please explain how did u make this tree? in which sequence have you taken the data..

for example if a sequence  is 1,2,3,4,5,6,7,8

then tree would be like:-

1 2(right child of 1), 3(right child of 2), 4(right child of 3) and so on...

1

\

2

\

3

0
How can you construct the tree with out in-order traversal output of the tree?
0
How did u construct the tree
+2
Construct all tree by taking Inorder and preorder (given in  options) .Then find out which tree is giving the correct inorder.
0

how did you draw the above tree isnt it wrong?

0
@manojk ; your argument is contradictory
+2 votes
answer D
answered by Loyal (8.8k points)
+2
We can also construct bst for each option and find its preorder we will see that option d is right
0 votes
The best thing is to draw the tree and see whether it is following preorder rule or not just like

A) when we traverse in preorder after making tree, 6 comes before 8. so false

B) when we traverse in preorder after making tree, 4 comes before 6. so false

C) when we traverse in preorder after making tree, 1 comes before 4. so false

D) it is right sequence it follow preorder rule.
answered ago by Active (1.3k points)
Answer:

+13 votes
3 answers
1
+14 votes
3 answers
2
+12 votes
2 answers
3
+26 votes
2 answers
4
+26 votes
4 answers
5
+20 votes
2 answers
6
+1 vote
0 answers
7