in Programming
1,631 views
0 votes
0 votes
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
in Programming
by
5 points
1.6k views

2 Answers

1 vote
1 vote

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

by
751 points
0 votes
0 votes
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.