edited by
37,209 views
48 votes
48 votes

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$
edited by

7 Answers

Best answer
65 votes
65 votes

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.

Correct Answer: $D$

edited by
18 votes
18 votes

Answer: D

The tree is:

7 votes
7 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.
Answer:

Related questions