0 votes
135 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.

in DS
recategorized | 135 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

+1 vote
2 answers
1
+1 vote
1 answer
2
0 votes
1 answer
3
+1 vote
1 answer
4
+4 votes
3 answers
6
0 votes
3 answers
7