CareerCup

step 1: count the number of nodes in the tree ... in o(n) time.

step2: Make an inorder traversal for N/2 nodes.


time complexity O(n)
please correct me if some thing wrong...

if you augment the bst with the number of nodes on the left and right as you insert items into the bst, the median can be looked up in o(logn). The number of nodes can be maintained while insertion and deletion.

anyway, the solution is O(n) complexity as we need to go through the whole tree to find how many nodes on left side and how many on the right side.

Another solution might be ... try simultaneous inorder and a reverse inorder traversals and do them one node at a time.
Median = point where they meet or avg of points where they cross.

Order Statistics of Tree for Median of a BST

Step 1: Add another ‘size’ variable which is to store the size of the nodes in the sub trees.
Step 2: Create the tree and find the size. When completion of tree, return the size stored at Root, which will be the total number of nodes in the tree.
Step 3: If the total number of nodes is n and it is an odd number, then n/2th number is the median, else (n/2 th number +(n/2+1) th number )/2 is the median
Step 4: Use order statistics to find the n/2 the largest number for odd, n/2 and (n/2+(n/2+1) )/2 for even.
After creating the Tree with size variable, use the following to find the largest number.
public Node KThLargest(int k, Node t)
{
int rsize = 0;

if (t == null)
return null;

// size of right subtree
if (t.Right != null)
rsize = t.Right.Size;

if (k == rsize + 1)
return t;

if (k <= rsize)
return KThLargest(k, t.Right);
else
return KThLargest((k - rsize - 1), t.Left);
}
O(n) is the complexity.