Made Easy Test Series

Question

Select the incorrect statement.

Binary search trees (regardless of the order in which the values are inserted into the tree):

a. Always have multiple links per node.

b. Can be sorted efficiently.

c. Always have the same shape for a particular set of data.

d. Are nonlinear data structures.

How a is right?

ANS: c. Always have the same shape for a particular set of data

Answer 1

c is Incorrect.

BST cannot have same shape for particular set of data

 

Suppose you have to insert three elements

Input sequence matters in a BST

 

Suppose you have input sequence

1,2,3

BST will be

1

       2

               3

 

But if your input sequence is 3,2,1

Then your tree will be like

                 3

       2

1

 

 

For particular set {1,2,3} you can have many BST possible and shape changes.

 

Now answering your doubt

 

A BST with a set of elements always have multiple links per node. 

This statement is correct because A BST is a Structure where each node has more than 1 links, one pointing to the left sub tree and one pointing to the right sub tree

 

Struct node *BST{

int data

node *left;

node *right;

}s;

 

Thanks

Answer 2

Option a

always have multiple links per node – Confusing but true

Actually there is always two OUTGOING pointers even in leaf nodes, the only difference is that in leaf nodes these two left , right outgoing pointers are null

 

option b. Can be sorted efficiently

best case tc nlogn

worst n^2 hence on average its efficient

 

option c)  always same shape WRONG

1

    2

         3

 OR

       3

    2

 1

option d) non linear data structure: true