RSS Feed

techInterview Discussion

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?
Constraints:
-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.

Whats the data structure used? Does it have any parent pointer?

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).

Why cant we apply the approach of finding the middle node of a linked list in this case?

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.)

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.

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.

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!!

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

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

else
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