The Gateway to Computer Science Excellence
0 votes

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.

in DS by
recategorized by | 164 views

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


Deletion takes O(log n) so O(n) also correct.  It's True
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.
It says it's the difference. So why should sign matter?
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 .....


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

1st one is correct one
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.

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
52,345 questions
60,493 answers
95,304 users