Interview Questions And Answers 
-
How to find median of a BST?
constraint: without storing it in a linear data structure by inorder traversal?832 Views |
(4 votes, avg: 2.75)
Loading ...
Answers »
Our Sponsors
Our Sponsors
isn’t it same problem as finding the kth largest element in a given list whereby we make a BST with every node keeping count of # of lements in its left subtree.
Find the no. of elements on the left side.
If it is n-1 the root is the median.
If it is more than n-1, then it has already been found in the left subtree.
Else it should be in the right subtree.
initialize med to -1 and call as
findMed(root, n/2, &med); //assume n is known
int findMed(node*root, int n, int* med)
{
if(!root || nleft, n, med);
if(m>=n)
{
return INF; //found
}
if(m==n-1)
{
*med=*root;
return INF;
}
p=findMed(root->right, n-m-1, med);
if(p+m+1>=n) return INF; //found
}
regards,
J1gs4w
I think first we need to find the number of elements in the BST by any traversal technique.then using the inoder traversal go to nth/2 ele,ent that will be the median
Leave an Answer/Comment