Balanced binary search tree

Question

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)

Comments

@Joshi, shreshtha :

To find the $9_{th}$ largest element -:

As the tree is balanced, the $9_{th}$ largest will be present at the rightmost subtree of height $9$.

i.e if array index is started from $1$ , then it is present at $ar[2^{8+1}-1]$ where h=height of tree..

hence finding $9_{th}$ largest cn be done in $O(1)$ ..isn't it ?

---

@sourav
is AVL tree constructed using array ?

---

Its not always true 9th largest element is present upto 9th level.

Answer 1

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