972 views
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

# 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.

## 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

by
751 points
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
by
5 points