Interview Questions And Answers 
-
How to find median of a BST?
constraint: without storing it in a linear data structure by inorder traversal?6,789 Views |
(11 votes, avg: 3.82)
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
The answer by jigsaw wont work for unbalanced BST
Execute two InOrder traversal, the first one runs as the double speed the second one. It means the first one visits two nodes while the second one visits one nodes.
So when the first one finish traverse, the second one point the mid value!
Start two inorder traverse, one to the left, one to the right, at the same pace, until they meet.
the solution by yuyu does not seem to work. how can they ever meet if one is on left and one is on right??
I suppose yuyu meant traversal in a descending order.. (Right-Node-Left).
Leave an Answer/Comment