recategorized by
933 views
5 votes
5 votes
A balanced binary search tree of n nodes,the number of steps needed to find and remove the 9th largest element in the worst case?

(Please mention the algorithm followed)
recategorized by

1 Answer

0 votes
0 votes
A balanced binary Search tree is tree with Balanced Height so it cant be skewed. The very rightmost element is the Largest Element.And in standard Balanced Binary Search tree no Duplicates are Allowed SO:-

We could use something like:- (Rough Idea)

Function(RootNode){

for ( i = 0 to 9){

node = RootNode;

if(node == NULL){

    printf("No 9th Large element Present")  

     return;

}

while(node->right != NULL)

        node = node->right;

DeleteNode(node)       //This function will delete the Specfied node from the Balanced Binary Search tree and will also again balance the tree ---->O(logn)

}

printf("9th largest element deleted");

}

 

This loop will execute 9 times and larget element will be Deleted.

Time complexity O(9logn) = O(logn) + C

Related questions

0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
pradeepchaudhary asked Aug 19, 2018
19,111 views
8. What are the worst case and average case complexities of a binary search tree?a) O(n), O(n)b) O(logn), O(logn)c) O(logn), O(n)d) O(n), O(logn)