Microsoft Interview Question Software Engineer / Developers

  • microsoft-interview-questions
    0
    of 0 votes
    25
    Answers

    Is this possible?

    A BST is given. Without using any extra memory AND WITHOUT USING recursion.

    1. Convert the BST into Sorted single Linked List.
    2. Convert the Sorted Linked List in (1) to exactly identical original BST.

    Suppose tree is:


    10
    / \
    1 N
    / \
    N 5
    / \
    2 N
    / \
    N 4

    - Name on September 20, 2012 in India for Ad Center Report Duplicate | Flag
    Microsoft Software Engineer / Developer Algorithm

Team: Ad Center
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

- Tommy Boy on September 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Tommy Boy on September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Name on September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vincent on September 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 on September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{
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 on September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity to convrt back looks to be o nlogn

- Ashupriya on September 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on September 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- sonesh on November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kevinspirit7 on February 27, 2013 | Flag
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;
};

- Name on September 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No.

- loveCoding on September 20, 2012 | Flag Reply
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...

- fgao on September 21, 2012 | Flag Reply
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

- Name on September 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Tommy Boy on September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhijit on September 21, 2012 | Flag
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

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

- Name on September 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Abhijit on September 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks Tommy.

- Name on September 21, 2012 | Flag Reply
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!

- Name on September 22, 2012 | Flag Reply
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....

- Dhuriya on September 26, 2012 | Flag Reply
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;
}

- wonderow on September 29, 2012 | Flag Reply
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;
				}
			}
		}
	}

- Kevin on March 07, 2013 | Flag Reply
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);
}
}

- Dhuriya on September 26, 2012 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More