Microsoft Interview Question Software Engineer / Developers
Team: Ad Center
Country: India
Interview Type: In-Person
I gave a go at implementing this last night, and while I was able to do the Morris Traversal I was not able to find a solution on how to reconstruct the exact BST with the list I was able to create. I am not sure that there is a solution for reconstructing the BST from just a simple linked list.
@ Eugene
I solved the 2nd part LL -> Original BST
Let each node in Single Sorted LL point to its parent in Original BST. Now with this LL we could create Original BST.
The only problem left with me is BST -> Sorted LL (with each node pointing to parent)
Be honest, for the second part, I think it is impossible.The sorted LL is just an inorder of the original tree. Given an inorder of the bt, we may be able to construct more than one trees
Lets take BST example.
5
3 7
1 4
2
Now form Sorted Single Link List from one pointer (say right), and make left pointer point to parent of every node.
How, to do this is still not solved. But I assume you are able to make BST -> LL in this manner.
1 -> 2 -> 3 -> 4 -> 5 -> 7 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | | | |
3 1 5 3 NULL 5 (left pointer pointing to parent)
Now make a tree from this Linked Lisk.
1. Find root of BST, A node will null parent in LL will be root of BST, 5.
Take 5 out of LL.
1 -> 2 -> 3 -> 4 -> 7 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | | |
3 1 5 3 5 (left pointer pointing to parent)
BST:
5
N N
2. Traverse LL from right to left.
Traverse 7. If 7's parent (5) is in BST, put 7 in BST
LL:
1 -> 2 -> 3 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | |
3 1 5 3 (left pointer pointing to parent)
BST:
5
N 7
N N
3. Traverse LL.
Traverse 4. If 4's parent (3) is in BST, no action.
LL:
1 -> 2 -> 3 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | |
3 1 5 3 (left pointer pointing to parent)
BST:
5
N 7
N N
4. Traverse LL.
Traverse 3. If 3's parent (5) is in BST, put 3 in BST.
LL:
1 -> 2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | |
3 1 3 (left pointer pointing to parent)
BST:
5
3 7
N N N N
5. Traverse LL.
Traverse 2. If 2's parent (1) is in BST, no action.
LL:
1 -> 2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | |
3 1 3 (left pointer pointing to parent)
BST:
5
3 7
N N N N
6. Traverse LL.
Traverse 1. If 1's parent (3) is in BST, put 1 in BST.
LL:
2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| |
1 3 (left pointer pointing to parent)
BST:
5
3 7
1 N N N
N N
7. Traverse LL.
Traverse 4. If 4's parent (3) is in BST, put 4 in BST.
LL:
2 -> NULL (right pointer pointing to next in Sorted Liked List)
|
1 (left pointer pointing to parent)
BST:
5
3 7
1 4 N N
N N N N
8. Traverse LL.
Traverse 2. If 2's parent (1) is in BST, put 2 in BST.
LL:
NULL (right pointer pointing to next in Sorted Liked List)
(left pointer pointing to parent)
BST:
5
3 7
1 4 N N
N 2 N N
N N
{
Lets take BST example.
5
3 7
1 4
2
Now form Sorted Single Link List from one pointer (say right), and make left pointer point to parent of every node.
How, to do this is still not solved. But I assume you are able to make BST -> LL in this manner.
1 -> 2 -> 3 -> 4 -> 5 -> 7 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | | | |
3 1 5 3 NULL 5 (left pointer pointing to parent)
Now make a tree from this Linked Lisk.
1. Find root of BST, A node will null parent in LL will be root of BST, 5.
Take 5 out of LL.
1 -> 2 -> 3 -> 4 -> 7 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | | |
3 1 5 3 5 (left pointer pointing to parent)
BST:
5
N N
2. Traverse LL from right to left.
Traverse 7. If 7's parent (5) is in BST, put 7 in BST
LL:
1 -> 2 -> 3 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | |
3 1 5 3 (left pointer pointing to parent)
BST:
5
N 7
N N
3. Traverse LL.
Traverse 4. If 4's parent (3) is in BST, no action.
LL:
1 -> 2 -> 3 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | | |
3 1 5 3 (left pointer pointing to parent)
BST:
5
N 7
N N
4. Traverse LL.
Traverse 3. If 3's parent (5) is in BST, put 3 in BST.
LL:
1 -> 2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | |
3 1 3 (left pointer pointing to parent)
BST:
5
3 7
N N N N
5. Traverse LL.
Traverse 2. If 2's parent (1) is in BST, no action.
LL:
1 -> 2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| | |
3 1 3 (left pointer pointing to parent)
BST:
5
3 7
N N N N
6. Traverse LL.
Traverse 1. If 1's parent (3) is in BST, put 1 in BST.
LL:
2 -> 4 -> NULL (right pointer pointing to next in Sorted Liked List)
| |
1 3 (left pointer pointing to parent)
BST:
5
3 7
1 N N N
N N
7. Traverse LL.
Traverse 4. If 4's parent (3) is in BST, put 4 in BST.
LL:
2 -> NULL (right pointer pointing to next in Sorted Liked List)
|
1 (left pointer pointing to parent)
BST:
5
3 7
1 4 N N
N N N N
8. Traverse LL.
Traverse 2. If 2's parent (1) is in BST, put 2 in BST.
LL:
NULL (right pointer pointing to next in Sorted Liked List)
(left pointer pointing to parent)
BST:
5
3 7
1 4 N N
N 2 N N
N N
}
@Name , please consider following points
1) It is not a singly linked list
2) your algorithm require o(n*n*n) time, because you are scanning the list n times, in worst case list size size may be reduced by just 1, and then searching in the tree for parent node, that can also require O(n) time in worst case, so total count to O(n*n*n) complexity, certainly not excepted
3) How can you move in singly list from right to left, without using recursion
4) If you are doing it like deleting node from list and inserting into BST, then this will not be excepted at all as per your question because by deletion we can't delete pointer, we only able to delete not data there always be a pointer which is remaining their, If not then, you have to explain how you can move in the list, (one solution could be add element at beginning of list and keep a pointer which tells the start point)
5) and may be more
BSTToLinkedList is possible by Morris traversal.
LinkedListToBST is not possible because the LinkedList is regarded as a inorder traversal sequence, we may need another postorder or preorder sequence to reconstruct a BST. With only inorder sequence, there must be more than one BST can be built.
I had been asked this question at MS IDC Bangalore (Ad Centre Group).
Tommy & Fgao,
The complete question is following, Is it feasible to achieve this using Morris Traversal?
BST -> Sorted Single Linked List -> Back to Identical Original BST
I believe that the only trick to this is finding the right place in your traversal to add the node to the list. sorted seems strange since essentially you need to preserves the same order of that the BST needs for re-creation, but I presume this can be done similar to an inorder traversal using Morris's algorithm. To be honest I have not yet implemented this, when I get some time I will give it a go and post the results here.
"sorted seems strange since essentially you need to preserves the same order of that the BST needs for re-creation, but I presume this can be done similar to an inorder traversal using Morris's algorithm" -- This should not be an issue as inorder traversal of a BST will always result in sorted sequence.
Please see this example. Morris Traversal doesn't look to work for this ques.
BST -> Sorted Single Linked List -> Back to Identical Original BST
5
3 7
Linked List
3 -> 5 (5 is right child of 3)
5 -> 7 (7 is right child of 5)
7 -> N (N means NULL)
BST from above LL is not same as original
3
5
7
Use a few temp pointers:
Node *ConvertBST(Node *pRoot)
{
Node *pCurrentMin, *pPrevious, *pPreviousMin = NULL;
Node *pNewRoot = NULL;
while (pRoot != NULL)
{
pCurrentMin = pRoot;
pPrevious = NULL;
// Until reach the most left
while(pCurrentMin->pLeft != NULL)
{
pPrevious = pCurrentMin;
pCurrentMin = pCurrentMin->pLeft;
}
// New root is the minimum
if (pNewRoot == NULL)
{
pNewRoot = pCurrentMin;
}
// If root is the minimum
if (pPrevious == NULL)
{
pRoot = pRoot->pRight;
}
// Set min->right to previous->left
else
{
pPrevious->pLeft = pCurrentMin->pRight;
}
// Move min to end of the new stack
if (pPreviousMin != NULL)
{
pPreviousMin->pRight = pCurrentMin;
}
pPreviousMin = pCurrentMin;
}
return pNewRoot;
}
BST->LinkedList is possible by using Morris's traversing
LinkedList -> BST is not possible, I think. Because you could not locate which one is the root of this tree. So you will have multiple choices to create this tree.
private void morrisTraversalT(TreeNode root){
if(root == null){
return;
}
TreeNode current = root;
TreeNode pre = null;
while(current != null){
if(current.left == null){
System.out.print(current.element + " ");
current = current.right;
}else{
//find the predecessor of current
pre = current.left;
while(pre.right != null && pre.right != current)
pre = pre.right;
//make current as right child of its inorder predecessor
if(pre.right == null){
pre.right = current;
current = current.left;
}
else{
//revert the changes made in if part to restore the original tree
pre.right = null;
System.out.print(current.element + " ");
current = current.right;
}
}
}
}
Yes this is possible using what is called Morris Traversal, which borrows from the idea of a threaded BST. Do a search on Morris Traversal and you can see how to traverse a tree without recursion and without any additional memory.
- Tommy Boy September 20, 2012This is a pretty tricky question to be honest, not one I would expect in any standard interview, even at MS