Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Use Morris Traversal. The idea is -

1. Initialize root as current
2. while current is not NULL
	a) if current has no left child
		- print current and set current = current.right
	b) else 
		- set current as rightmost node of left child

Source Code:

void inorderWithConstantSpace(TreeNode *root) {
	if(!root) return root;	
	TreeNode *current = root;
	while(current) {
		if(current->left) {
			TreeNode *leftChild = current->left;
			TreeNode *tmp = leftChild;
			TreeNode *rightMost;
			while(leftChild) {
				rightMost = leftChild;
				leftChild = leftChild->right;
			}
			rightMost->right = current;
			current->left = nullptr;
			current = tmp;
		} else {
			printf("%d ", current->value);
			current = current->right;
		}
	}
}

- Kaidul Islam May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hello Kaidul Islam,
I have tested your code but it did not work. Are you considering a BST?
I think this is not a BST, else, would be easy to do that...

Output from your algorithm developed in Java:

14
12
17
10
7
9
6

/**
 * Created by sky on 5/5/15 from Kaidul Islam algorithm
 */
public class RegularTreeInOrder {
    private static final class Node<T> {
        private T value;
        private Node<T> right;
        private Node<T> left;

        public Node(T value) {
            this.value = value;
        }
    }

    public static <T> void inorderWithConstantSpace(Node<T> root) {
        if (root == null)
            return;

        Node<T> current = root;

        while(current != null) {
            if(current.left != null) {
                Node<T> leftChild = current.left;
                Node<T> tmp = leftChild;
                Node<T> rightMost = null;

                while(leftChild != null) {
                    rightMost = leftChild;
                    leftChild = leftChild.right;
                }

                rightMost.right = current;
                current.left = null;
                current = tmp;
            } else {
                System.out.println(current.value);
                current = current.right;
            }
        }
    }

    public static void main(String[] args) {
        Node<Integer> root = new Node<>(10);
        root.right = new Node<>(9);
        root.right.right = new Node<>(6);
        root.right.left = new Node<>(7);

        root.left = new Node<>(12);
        root.left.right = new Node<>(17);
        root.left.left = new Node<>(14);

        inorderWithConstantSpace(root);
    }
}

- Felipe Cerqueira May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Felipe,

Thanks for your trial. your inserted tree is not a BST. if 10 is a root, 9 can't be its right child. Right child has to be greater than root.

- Kaidul Islam May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Felipe, the output is correct

- gen-x-s May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Gr8 sol'n.
Felipe == wrong. The output is correct for in-order traversal.
What you talking about BST ? the quesrtion is about a regular binary tree, not BST or full tree etc. Don't say wrong things.

- gen-x-s May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am sorry. But the output is not correct.
A tree where node.right > node and node.left < node is a Binary Search Tree.
I understood from the problem that we dont have a BST. Is is a regular tree.
Where We can have arbitrary values everywhere.

So, from a regular tree, how do you print the elements in order?

As you can see, using an arbitrary tree, the output is not sorted:

14
12
17 > 12 (wrong)
10
7
9
6

Walking thru a BST in order is very easy:

dfs(node.left)
print value;
dfs(node.right);

But, this is not the case...

- Felipe Cerqueira May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Felipe: Inorder traversal doesn't mean the output will be sorted from Binary tree. It simply means print LeftNodeRight. InOrder can be used on a BinaryTree or n-tree after a little modification.

However, if its a Binary Tree is a BST; Inorder will give sorted values otherwise not.

- pk May 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution will change the original tree. Is there a way without changing original tree

- pc May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I had this question a long time ago, and managed to pseudo-solve it. But now thinking about how to code it, I can't even imagine how it could possibly work.

- Jack Le Hamster May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

static void printInorder(Node root) {
                while (root != null) {
                        while (root.left != null) {
                                Node p = root;
                                while (p.left.left != null) {
                                        p = p.left;
                                }
                                print(p.left.value);
                                p.left = p.left.right;
                        }
                        print(root.value);
                        root = root.right;
                }
        }

- Anonymous May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In order traverse the tree, for each node visit, swap the node data with the minimum node data in the tree. To find minimum, we need to have another tree traversal.
Since extra space is not allowed, we are not able to use hash table to indicate which nodes are swapped (containing min in the right position), we need to slightly modify the node structure to have a flag indicating whether the data is "swappable" or not.
At the end of the process, the tree becomes a BST and takes O(n^2) time complexity.

However, any in order traversals (recursive or non-recursive) take O(n) space which violate the requirement. Therefore, I think the question is asking O(1) space for temporary data storage.

- Daniel May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use heapify concept of Min heap & then print Min element ?? correct me if i'm wrong ?

- Ram May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It would required O(n) space. Sadly, I don't think it is a possibility.
What I am thinking is, there is a space limit but nothing was said about running time.
In N^2 you would be able to traverse the tree marking the printed node (smallest one) and then, repeating the process.

In the end, you should print the nodes in order.

- Felipe Cerqueira May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Heapify takes O(1) space complexity. This should work.

- Alex May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution would be valid only if it is a complete binary tree

- teli.vaibhav May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) space would be possible traversing the tree N times and marking the selected nodes.

- Felipe Cerqueira May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Flagging notes is actually taking O(n) space since you'd have to add extra data on each node.
By changing the node without taking extra space, you'd have to change the left/right pointers. (So that's another hint.)

- Jack Le Hamster May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. I though about flaging to avoid delete because I was thinking the cost to remove from a BST (where you should rebalance the Tree).
For a regular tree, you can remove in constant time.

So, traverse in O(n^2) and remove the sorted (printed) numbers.

- Felipe Cerqueira May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just fixing the past answer: Not Queue but Tree.

- Felipe Cerqueira May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the tree is a complete binary tree. We can suggest a Heap solution.
Now talking about a general case where it may or may not be a complete BT:
1) Find the smallest element in the tree
2) Delete the smallest element you found & print the same
3) Rebalance the tree to ensure it still remains a BST.
Repeat steps 1 to 3 until you are done with all elements.
The algorithm is inefficient with O(n^2) time complexity but the desired O(1) space

- teli.vaibhav May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Morris Traversal´╝îhere is the AC code of Leetcode #94

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode *pre = NULL, *cur = root;
        vector<int> res;
        while (cur != NULL) {
            if (cur->left == NULL) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) {
                    pre = pre->right;
                }
                if (pre->right == NULL) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    res.push_back(cur->val);
                    cur = cur->right;
                } 
            }
        }
        return res;
    }
};

- Eason May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basicly every method that uses a stack or recursion is not O(1) in space. So if you can modify the tree, you just need to make a simple node rotation so in the end your tree will look just like a list. Code should be something like this:

def inorder_O1_Space(s):
        current = s
        while current != None:
                if current.left != None:
                        # rearrange the tree
                        child = current.left
                        current.left = child.right
                        child.right = current
                        current = child
                else:
                        print current.value
                        current = current.right

- kef May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Morris algorithm can solve this problem. Is there any way to pre-order or post-order in O(1) space by Morris algorithm?

- zhanlongbo May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Write a function to delete a node like: void delete(Node n);
2. Write a function to find the most left node like: Node FindMostLeftNode(Node n);
3. Write a function to check the node is a leaf like: bool isLeaf(Node n);
4. Write a function to output the node like: void output(Node n);
5. Find the most left node, if the node is a leaf, remove it, if not, let the node=node.right ;

void InorderTraverse(Node root)
{
	Node mostLeft=FindMostLeftNode(root);
	while(mostLeft!=null)
	{
		output(mostLeft);
		if(isLeaf(mostLeft))
		{
			delete(mostLeft);
		}
		else
		{
			mostLeft=mostLeft.right;
		}
		
		mostLeft=FindMostLeftNode(root);
	}
}

- Jeff May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Write a function to delete a node like: void delete(Node n);
2. Write a function to find the most left node like: Node FindMostLeftNode(Node n);
3. Write a function to check the node is a leaf like: bool isLeaf(Node n);
4. Write a function to output the node like: void output(Node n);
5. Find the most left node, if the node is a leaf, remove it, if not, let the node=node.right ;

void InorderTraverse(Node root)
{
	Node mostLeft=FindMostLeftNode(root);
	while(mostLeft!=null)
	{
		output(mostLeft);
		if(isLeaf(mostLeft))
		{
			delete(mostLeft);
		}
		else
		{
			mostLeft=mostLeft.right;
		}
		
		mostLeft=FindMostLeftNode(root);
	}
}

- Jeff May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is simple:
- starting from root check all nodes, if curr node has left child
	if has: move curr node as right child in most right node in left subtree
		   and use curr parent node as parent for left node
	if not: move current to right child
- print tree where every node has only right node

Note: root node can be changed, and eventually it will be the first node we have to print.

public static void printInOrder(Node root){
        if (root == null) return;
        boolean isReady = false;

        while (!isReady){
            isReady = true;
            Node curr = root;
            while(true){
                if (curr.L != null){
                    isReady = false;
                    curr.L.P = curr.P;
                    if (curr.P != null){
                        curr.P.R = curr.L;
                    } else {
                        root = curr.L;
                    }
                    Node mostRight = findMostRight(curr.L);
                    mostRight.R = curr;
                    curr.P = mostRight;
                    curr.L = null;
                } else {
                    curr = curr.R;
                    if (curr == null) break;
                }
            }
        }
        Node curr = root;
        while (curr != null){
            print(curr);
            curr = curr.R;
        }
    }

    private static void print(Node n) {
        System.out.printf("%s ", n.val);
    }

    private static Node findMostRight(Node root){
        Node curr = root;
        while (curr != null){
            if (curr.R == null) return curr;
            curr = curr.R;
        }
        return null;
    }

- prosto.mail May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is simple and straigh forward in-order traversal as shown bellow if O(1) is required without counting the call stack.

public static void InOrderTraversal(Node root)
{
	if(root == null)
		return;
	
	InOrderTraversal(root.Left);
	Console.WriteLine(root.Data);
	InOrderTraversal(root.Rigth);	
}

Now stating that the call stack counts towards the O(1). Here the best way is to flatten the three into a list where the Next is the Right. Adding the parent node to the right most of the left side.

Note:

Notice that in the code bellow keeps integrity of tree fixing the new Right of the previous node after performing the flatening and also return the new root element.

This is not necesary for the algorithm as I could easily don't care about the reference integrity of the tree during traversal so no need for caring about the prevParent nor returning the new root.

public static void InOrderTraversalO1(Node root)
{
	
	Node parent = root;
	Node newRoot = null;

	// Dummy node to not check for null
	Node prevParent = new Node();

	while(parent != null)
	{
		if(parent.Left == null)
		{
			Console.WriteLine(parent.Data);

			if(newRoot == null)
			{
				newRoot = parent;
			}

			prevParent = parent;
			parent = parent.Right;
		}
		else
		{
			Node left = parent.Left;
			Node rightMost = left;

			// Find right most
			while(rightMost .Rigth != null)
			{
				rightMost = rightMost .Right;	
			}

			
			rightMost.Right = parent;
			parent.Left = null;

			parent = left;

			// Keep integrity 
			prevParent.Right = parent;
		}
	}
	
	return newParent;
}

- Nelson Perez May 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

After thinking more about my own question ;-P, I think there's this one solution that seems that it might work, though I'd have to test it:
Step 1: Keep rotating the tree clockwise until there's no left
Step 2: Output root, move root to root right
Step 3: Repeat step 1.

There are some details about the question though (and this is just what I kinda remember from the original interview question, feel free to just interpret the problem as it is written).
#1 - call-stacks do count as space, so recursion is out of the picture for O(1) space.
#2 - I'm pretty sure the solution had to be O(n) time as well.
#3 - This part I can't remember for sure, but I thought we had to restore the tree in its original state after the traversal (in which case my solution here wouldn't even work). Now I could be wrong about this.)

- Jack Le Hamster May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution

Current <= Root;
while(Current is not null)
    if Current -> left is not null
         Current = Current -> Left;
    else
         Print Current.Value
         Current.Printed = true;
         If Current -> Right is not null
             Current = Current -> Right;
         else
              Current = Current -> Parent;

- sonesh June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Can we just use Heapify concept of Min Heap to modify the tree and then output Min value from the tree ??

- Ram May 05, 2015 | Flag Reply


Add a Comment
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.

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