Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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);
}
}
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.
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.
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: 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.
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.
Can we use heapify concept of Min heap & then print Min element ?? correct me if i'm wrong ?
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.
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.)
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.
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
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;
}
};
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
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);
}
}
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);
}
}
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;
}
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;
}
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.)
Use Morris Traversal. The idea is -
Source Code:
- Kaidul Islam May 05, 2015