## Microsoft Interview Question for Program Managers

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

Here's the complete code

int maxDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = maxDepth(root->left) + 1;
int rDepth = maxDEpth(root->right) + 1;

return ((ldepth>rDepth) ? ldepth:rdepth);
}
}

int minDepth(Tree* root)
{
if (root == NULL) return 0;
else
{
int ldepth = minDepth(root->left) + 1;
int rDepth = minDEpth(root->right) + 1;

return ((ldepth>rDepth) ? rdepth:ldepth);
}
}
bool isDiffMoreThanTwo(Tree* root)
{
return ((maxDepth(root) - minDepth(root)) >=2 );
}

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

I think the algorithm can be modified a little bit to be interrupted as soon as we find that any (Min + 1) < Max.

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

Simple DFS with keeping min and max lengths.

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

1. Firstly, we need to enlist all the leaf nodes and their levels in the tree. In order to do this, do a Level order Traversal on the Tree (using queue) and store all leaf node and their levels into a 2d array (by verifying if the node doesn't have child nodes and maintaining a level variable in the recursive level order traversal).
2. Now that we have 2d array of all leaf nodes and its level, we need to find all array elements, wherein difference of levels is 2 or more. O(n square) time complexity we can find all nodes differing by 2 or more. Any better approach, please share.

The level order traversal in binary tree can be brought about by

``````void LevelOrderTraversal(Tree myBinTree) {
Queue myQ = new Queue();
Tree myTree = myBinTree;
int level = 0;
while(myTree != null) {
if(myTree.leftChild == null && myTree.rightChild == null)
Insert <myTree, level> into the 2d array
if(myTree.leftChild != null)
myQ.add(myTree.leftChild);
if(myTree.rightChild != null)
myQ.add(myTree.rightChild);
myTree = q.delete(myTree); //deletes the current node and returns the next node in Q
level++;
}``````

//Have to code the algo to find the nodes differing by >1 levels.

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

You just making simple things complicated.
Do DFS of tree calucating minimum and maximum depth in parralel. Stop when max - min >= 2.
Solution is O(n) (well, we can do it in n^2, n^3 and so on :) )

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

Thats Right !!

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

@gevorgk: "Depth First Search of Binary tree"... Can you please elaborate on which kind of traversal do you intend to do. A pseudo code/algo would be great.. Didn't actually get it completely...
And how are you enlisting all the leaf nodes which differ by >1 level difference?

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

seee below...

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

gevorgk,
Depth first search won't work. because for nodes which has only one child min-depth will be that from no-child side but there is no leaf there.
I think a good approach would be to traverse Breadth first and keep track of levels by maintaining child count for a level added in queue. check each node while popping it whether it's leaf note down max and min levels of leafs.
you can quit the traversal in middle if question is to find out whether a certain difference of depth for leaves exist in tree

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

Ok, let me exlplain better. Question says wether there a ANY 2 leaf nodes, which differ by more than 1 level.
We will find the leaf with Min depth, and leaf with max depth. If the deifference is more than 1 - it means that we have at list one such pair. If difference is less than or equal to 1 - it means than there will be no such pairs, because the difference between min and max is largest one.

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

Guys, How about this. We use a global variable array of size two to keep tracking of min and max depth. Then we recursively DFS this Binary tree (don't forget to count the depth). When we hit the leaf node update min max can check max-min >=2. When it does flag the boolean so that we can eliminate unnecessary search. Then it O(N) in time with a use of O(2) array.

int depth[] = {0,0}; //global variable O(2)

bool check_leaf(Node &n_,int dep)
{
//base case
if(n_.Left == NULL && n_Right == NULL)
{
if(dep > depth)
depth = dep;
else if(dep < depth)
depth = dep;
if(depth - depth >= 2)
return true;
else
return false;
}else
{
if(n_.Left != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++))
return true; //stop unnecessary search
if(n_.Right != NULL) //Not a leaf node
if(check_leaf(n_.left,dep++));
return true; //stop unnecessary search
return false;
}
}

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

Another idea is to find the height of the left tree, find the height of the right tree. If the difference is more than 1, we return an error. The pseudo code will be some thing of this sort.

// Function return -1 if the difference is more than 1 level
// Function returns height of the tree other wise
// Assumptions : a properly constructed binary tree

int height(struct node** head)
{
// If head is equal to 0 return 0
//else t1 holds the height of the left tree t2 holds the height of the right tree
// if either of them is -1 that means some where down below there exits a sub tree with difference of more than 1 level. return -1
// if the difference is 0 or 1. then return the max height between either of the sub trees + 1
// else if the difference is 2 , return -1
}

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

int maxormin (int a, int b, int choice)
{
if (choice==0) return (a>b)?a:b;
if (choice==1) return (a<b)?a:b;
}

void height(node *root , int choice)
{
int maxht, minht;
if(root==NULL) return 0;

maxht= 1+maxormin(height(root->rlink),height(root->llink),0);
minht = 1+maxormin(height(root->rlink),height(root->llink),1)

if(maxht-minht > 1)
{
printf("yes > 1");
exit(0);
}
}

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

The exit condition in function height should be if(root->llink==NULL && root->rlink==NULL) return 0.

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

private void TraverseWithHeight (Node* t, int * min, int * max, int * height)
{
if(t == null) return;
if(t->left == NULL && t->Right == null)
{
If(height < min) min = height;
If(height > max) max = height;
Height --;
return; //leaf
}
Else
{
Height ++;
if (t->left != NULL)
TraverseWithHeight( t->left , min, max, height);
else
TraverseWithHeight( t->right , min, max, height);

}
}

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

cant we use hashing???
we`ll use a single dimensional array and use the hash value of the node as index..
in the array store the height of the node.
then it just is matter of finding 2 indices with diff greater than 1.
can be done in o(n) time and o(n) space??

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

Bool tree_diff_level(node *root)
{

Min = Min_height(root);
Max = Max_height(root);

If(max > min)
Return(true);
Else
Return(false);

}
Min_height(node *root)
{

If(root == NULL)
Return(0);
Return(min(Min_heigh(root->left), Min_height (root->right)),+1);

}

Max_height(node *root)
{

If(root == NULL)
Return(0);
Return(max(Max_heigh(root->left), Max_height (root->right)),+1);

}

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

excellent

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

Brilliant...:)

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

``````int checkDepth (Node *node)
{
if (node == 0)
return 0;

int left_len, right_len, difference;
left_len = right_len = difference = 0;

left_len = checkDepth (node->left);
right_len = checkDepth (node->right);

difference = abs (left_len - right_len);
if (difference > 1)
{
printf ("The tree has a difference of more than one");
exit (0);
}
else
return (MAX(left_len, right_len)+1);
}``````

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

``````public static boolean check(Node root){
return check(root,0) <= 1;
}

private static int check(Node node,int level){
if(node == null)
return level;

if(node.left != null && node.right != null)
return level;

int left = check(node.left,level+1);
int right = check(node.right,level+1);

return Math.abs(left-right);
}``````

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

``````public static boolean check(Node root){
return check(root,0) <= 1;
}

private static int check(Node node,int level){
if(node == null)
return level;
if(node.left == null && node.right == null)
return level;
int left = check(node.left,level+1);
int right = check(node.right,level+1);

return Math.abs(left-right);
}``````

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

``````Traverse each node using BFS
If CurrentNode.HasChildren() == false then // leaf node
Add_Node_To_Array_After_Level_Check(CurrentNode)
End If
Print all elements in the NodeList as they have a level difference more than 1

function Add_Node_To_Array_After_Level_Check(Node)
{
for(index = NodeList.Length-1 to 0)
{
if(Node.Level - NodeList[index].Level>1)
{
NodeList.Add(Node);
break;
}
}``````

}

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

Can be done in Scala easily:

``````object scratchie2 {
class Tree(val left: Tree, val right: Tree)

val root1 = new Tree(null, null)                //> root1  : com.test.scratchie2.Tree = com.test.scratchie2\$Tree@5efd2ebd
val root2 = new Tree(new Tree(null, null), null)//> root2  : com.test.scratchie2.Tree = com.test.scratchie2\$Tree@5858ba4b
val root = new Tree(new Tree(null, null), new Tree(null, new Tree(new Tree(null, null), null)))
//> root  : com.test.scratchie2.Tree = com.test.scratchie2\$Tree@292ebf3d
def isBalanced(tree: Tree): Boolean = {
if (tree.left == null && tree.right == null)
true
else if (tree.left != null && tree.right != null) {
isBalanced(tree.left) && isBalanced(tree.right)
} else if (tree.left != null && tree.right == null) {
tree.left.left == null && tree.left.right == null
} else {
tree.right.left == null && tree.right.right == null
}

}                                               //> isBalanced: (tree: com.test.scratchie2.Tree)Boolean

isBalanced(root1)                         //> res0: Boolean = true
isBalanced(root2)                         //> res1: Boolean = true
isBalanced(root)                                //> res2: Boolean = false

}``````

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

Here is just the code, use it in a worksheet or a class:

``````object scratchie2 {
class Tree(val left: Tree, val right: Tree)

def isBalanced(tree: Tree): Boolean = {
if (tree.left == null && tree.right == null)
true
else if (tree.left != null && tree.right != null) {
isBalanced(tree.left) && isBalanced(tree.right)
} else if (tree.left != null && tree.right == null) {
tree.left.left == null && tree.left.right == null
} else {
tree.right.left == null && tree.right.right == null
}

}
}``````

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

Do level order traversal - Check when encounter a leaf - Maintain min and max Leaf node level

O(n) time

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