The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
127 views

True / False:-

1.  : The difference between the number of nodes in a binary tree that have exactly two children and the number of leaf nodes is 1

2. Deletion of root of AVL tree will take O(n) time so that, resulted tree also have property of AVL tree.

I think first is false and second is true.. Because in first it should be -1 and in second it is correct as we can do in logn so o(n) is also correct.

Given answer is : 1 is true and second is false.

asked in DS by Boss (24.2k points)
recategorized by | 127 views
0
a)

Number of nodes with 2 children = x

Number of nodes with 1 children = y

Number of nodes with 0 children = z

Total Degree = 2*Edges

3x + 2y+ z -1(because of root node) = 2(x+y+z-1)

x - z = -1  Therefore False

b)

Deletion takes O(log n) so O(n) also correct.  It's True
0
There was some typeo in the explanation i gave in question.Anyways, i did the same way as you did,but they have given 1st are true and second as false.I think their answer is wrong.
0
It says it's the difference. So why should sign matter?
+1
ok we can say AVL tree deletion take O(logn) which is bounded by O(n) .....BUT here they said that deletion always create AVL tree .....not possible .....

AFTER DELETION OF NODE....AVL MAY LOST ITS PROPERTY....

and we may need to do rotations...

so 2nd statment is false....because the resultant tree after deletion may or may not be AVL...but they said it will...so false...

1st one is correct one
0
After a deletion of a node property of AVL cannot be lost. You will call AVLDelete(Root) and then its the responsibility of this function to maintain the property.Deletion itself means that node is deleted and property is maintained.Removing a node is a partial step of deleting a node and other step is to maintain AVL property

Please log in or register to answer this question.

Related questions

+1 vote
1 answer
2
0 votes
3 answers
7
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
49,541 questions
54,083 answers
187,206 comments
70,992 users