## Microsoft Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 6 vote

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.

This is a pretty tricky question to be honest, not one I would expect in any standard interview, even at MS

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@Name
Can you explain how you solved the second part i.e sorted LL to Original BST

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

{
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
}

Comment hidden because of low score. Click to expand.
0

Complexity to convrt back looks to be o nlogn

Comment hidden because of low score. Click to expand.
0

@name
complexity of u r soln is not O(n)
ll is not singly linked list

Comment hidden because of low score. Click to expand.
0

@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``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tree Node Structure is normal

typedef struct Node{
Node * left;
Node *right;
int Data;
};

Comment hidden because of low score. Click to expand.
0
of 0 vote

No.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes. we can use inorder tree traversal to traverse a tree in ascending order. And morris traversal is one kind of inorder tree traversal without recursion and without stack... Well, I think so...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Comment hidden because of low score. Click to expand.
0

If it's a sorted linked list, if we don't preserve any kind of other information, converting it to BST will always result in right-heavy tree.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks Tommy.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Anyone please share the code iff soln is feasible, without using extra memory!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Call inorder traversal .....your tree must be make from link list procedure....

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Void inorder( struct node* root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d",root->data);
inorder(root->right);
}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.