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

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

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

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.

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

Felipe, the output is correct

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.

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

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

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.

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

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

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.

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

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.

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 ?

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

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.

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

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

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

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

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.

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

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

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.

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

Just fixing the past answer: Not Queue but Tree.

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

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

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

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?

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

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

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;

Node curr = root;
while(true){
if (curr.L != null){
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;
}``````

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

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

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

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

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.