techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

[Microsoft]Median in BST[Tough one]

The question is easy without constraint do it within contraints.
Here's the original version of problem from MS

Given a BST (Binary search Tree) how will you find median in that?
-No extra memory.
-Function should be reentrant (No static, global variables allowed.)
-Median for even no of nodes will be the average of 2 middle elements and for odd no of terms will be middle element only.
-Algorithm should be efficient in terms of complexity.
Write a solid secure code for it.

No extra memory--u cannot use stacks to avoid recursion.
No static,global--u cannot use recursion and keep track of the elements visited so far in inorder.
Neophyte Send private email
Wednesday, September 16, 2009
Whats the data structure used? Does it have any parent pointer?
pbv Send private email
Thursday, September 17, 2009
Use left pointer to point its parent and right pointer to point to its successor and use the property of BST to update those pointers. 

Use a modified inorder traversal, where u update the above mentioned pointers. Left pointer gets updated when you reach that node (from its parent). Right pointer gets updated when you reach its successor. For finding successor you might have to go through left pointers (as current node ancestors will have its lp pointing to parent), and use BST property also to find successor of a node (if successor is not in its right child).  If a node has a right child its rp will get updated only after exploring its right child and will set to its successor.

Execution time O(n).
pbv Send private email
Thursday, September 17, 2009
Why cant we apply the approach of finding the middle node of a linked list in this case?
Friday, September 18, 2009
You can, but you need to find a way to convert the BST to a linked list without using recursion or extra space. (It can be done IIRC.)
d Send private email
Friday, September 18, 2009
with the above idea..we can use the algorithm to convert temporarily the BST into DLL , find median and then revert back to BST. So here goes another problem.

WAP to convert a DLL to BST(no extra space). So original problem is reduced now to this problem. Easier or tougher??? Anyways we can try.
Neophyte Send private email
Friday, September 18, 2009
Sorry didn't thought of it earlier...actually its not at all easy(perhaps impossible) to get the original BST with this approach so this can be ruled out.
Neophyte(Mohammad Akhtar Ali) Send private email
Friday, September 18, 2009
we can traverse the tree in inorder and for every node whose right pointer is NULL we can make it to point to its inordersuccessor. This operation would be O(n).
After this we can use the hare and tortoise as follows.

start with minimum.Let pointer p point to it.
Do a inorder traversal again this time point p to inordersuccesor of node pointer by p and fast pointer q to point to the succesor's succesor.Since we know we have inorder succesor of every node we never block from proceeding

Once we reach the last element node(max), we can return the node->data pointed by p.

There's one issue again that is to revert back the tree again to its original structure!!
Neophyte Send private email
Friday, September 18, 2009
The actual solution to the problem is in using morris inorder-a traversal algorithm which does the tree traversal without recursion or stacks. It does it through a temporary transformation of tree so that we can traverse it in ascending order (in case of BST) by just following the right pointers to a node. The transformed tree is such that for every node left child has already been visited.

So, a simple algo for median in BST would be:
1) Use any algo to count the number of nodes in the BST.Let it be n.
2) Use morris inorder(no recursion/no stacks-all constraint met ) to traverse the tree. For each node visited increment the counter.
a) If n is even then return avg(n/2,n/2+1)(counter == n/2)
b) If n is odd return when counter == (n+1)/2(1-based indexing)

The morris inorder algo takes care of reforming the tree to original while it is traversing the tree.

Summary of MorrisInorder

while (not finished)
if(node has no left descendant)
visit it and go to the right

make this node right child of the rightmost node in its left descendant
go to this left descendant


A beautiful implementation along with explanation is given in adam drozdek's data structures and algo book
Neophyte Send private email
Saturday, September 19, 2009

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz