GATE CSE 1997 | Question: 4.5

Question

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?

• A. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 8 \ 6$
• B. $5 \ 3 \ 1 \ 2 \ 6 \ 4 \ 8 \ 7$
• C. $5 \ 3 \ 2 \ 4 \ 1 \ 6 \ 7 \ 8$
• D. $5 \ 3 \ 1 \ 2 \ 4 \ 7 \ 6 \ 8$

Comments

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.

Answer 1

I simplified the answer as follows, this might help.

Answer 2

For options

All o/p are given starting from 5,

We know PreOrder= { ROOT  Left  Right  }

  Therefore Root is 5.

1.) Now make BST of root = 5

2.) Traverse for preOrder of the tree.

3.) Match with given options👍

Answer 3

1. Insert the node and draw a diagram
2. Make the mark on the left side(since it’s pre-order traversal) of the node for traversal later
3. Draw a line from the root counter wise. If the line meets the mark, output the number.
4. For example, option A with the sequence 5 3 1 2 4 7 8 6. However, the output is 5 3 1 2 4 7 6 8. Then it’s incorrect.