Saturday, 12 April 2014

Kth Largest of a BST

Given a BST of numeric values, find out the Kth largest of the tree.

/* create a new tree from a sorted array */
Node *addToBST(int arr[], int start, int end)
{
 if(end < start) return NULL;
 int mid = (start + end)/2;

 Node *r = new Node;
 r->data = arr[mid];
 r->left = addToBST(arr, start, mid-1);
 r->right = addToBST(arr, mid+1, end);
 return r;
}

void kthLarge(Node *root, int k)
{
    static int n=0;
    if(root == NULL)
    {
        return;
    }
    kthLarge(root->right,k);
    n++;
    if(n==k)
    {
        cout<<k<<"th max element is :"<<root->data<<endl;
        return;
    }
    kthLarge(root->left,k);
}

int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10,15,20,25,30,35,50};
Node *root = addToBST(a,0,15);
kthLarge(root,4);
}

No comments:

Post a Comment

AWS Data Pipeline Services

https://www.youtube.com/watch?v=tykcCf-Zz1M