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);
}
/* 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