## Microsoft Interview Question

Country: India

Comment hidden because of low score. Click to expand.
4
of 6 vote

``````#define MAX_IMBALANCE 2

bool isBalanced(node * root)
{
try
{
balanceCheck(root)
}catch(string & s)
return false;

return true;
}

//! returns the height of a node, throws a string if it is imbalanced
int balanceCheck(node * n)
{
if(!n)
return 0;

int lHeight = balanceCheck(n->left);
int rHeight = balanceCheck(n->right);

if(abs(lHeight - rHeight) >= MAX_IMBALANCE)
throw string("unbalanced");

return max(lHeight, rHeight) + 1;
}``````

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

Does anyone see anything wrong with my answer?

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

Apparently this is not correct solution:
Suppose we have a tree with the following edges:
1->2
2->3
1->4
4->5
5->6
4->7

This tree will be balanced according to your code, while in fact it isn't

Comment hidden because of low score. Click to expand.
4
of 8 vote

The idea is very simple, the difference of minimum height and the maximum height should not exceed 1.

``````int MaxHeight(Node* root) {
if (root == NULL)
return 0;

return 1 + max(MaxHeight(root->left), MaxHeight(root->right));
}

int MinHeight(Node* root) {
if (root == NULL)
return 0;

return 1 + min(MinHeight(root->left), MinHeight(root->right));
}

bool IsBalanced(Node* root) {
if (root == NULL)
return true;

return (MaxHeight(root) - MinHeight(root)) <= 1;
}``````

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

``````1
/  \
2    3
/       \
4         5
/            \
6             7``````

is the tree not balanced according to your code ?

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

this tree is not balanced, since balance of a binary tree is recursively defined, according to my code, the minimum height at root will be 2 and the maximum height will be 4.

You can see the code run here: ideone.com/aSaoZ

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

ya you are right!

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

``````your minheight function will return 1 for below tree but actual is 4

4
\
3
\
2
\
1``````

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

but maxheight will return 4
and
the difference is 3 so the tree is not balanced according to the code

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

minheight for the tree you describe _is_ 1, not 4

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

how come min height is 1 can you explain?
height is distance from root to leaf node right? there is only one root to leaf node path is there. So, max height and min height is same that is 4.

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

I guess root node is also counted then there's no left leaf, it returns 1

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

by ur code wether dis tree is balanced or not...

1
/ \
2 3
/ / \
4 5 6
/ \
7 8
comment........

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

by ur code wether dis tree is balanced or not...
********1
******2*****3
****4*****5****6
**************7**8

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

@Anonymous this tree is not balanced (min height = 2, max height = 4), but if Node 2 has a right child, this tree becomes balanced

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

but as per the rule of balance ..
dis tree is balance..
correct me if i m wrong..
comment..

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

from wiki: "A balanced binary tree is commonly defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1"

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

Your solution works, but needs to traverse the tree twice.

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

you first need to ask the interviewer what should be the height difference between left subtree and right subtree for tree to be imbalance
(this is just to show the interviewer that you are not directly assuming anything in questions)

here I am assuming that if difference between height of left subtree and right subtree is more than 1 then out tree is imbalanced
i.e.if(abs (leftHeight - rightHeight ) > 1)
return FALSE;

here is the full code

``````#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define TRUE 1
#define FALSE 0

struct node
{
int data;
struct node *left;
struct node *right;
};

typedef struct node* Node;

Node newNode(int data)
{
Node temp = (Node)malloc(sizeof(Node));
temp->data = data;
temp->left = temp->right = NULL;

return temp;
}

void insert(Node *head , int data) //Passing address of node because its data is being editted
{

else
{
else
}

}

int returnMax(int a, int b)
{

return a>b?a : b;
}

{
{
*height = 0;
return TRUE;
}

int leftHeight,rightHeight=0;
int leftTree,rightTree;

if(abs(leftHeight-rightHeight) > 1)
return FALSE;

//if left Subtree and right subTree are balanced
if(leftTree == TRUE && rightTree ==TRUE)
{
*height = returnMax(leftHeight,rightHeight)+1;
return TRUE;
}
return FALSE;
}

{
int height = 0;
}

int main()
{

isBalancedTree==TRUE?printf("Balanced") : printf("Not balanced");

return 0;
}``````

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

Hi,
if(leftTree == TRUE && rightTree ==TRUE) --> Is this condition really required???
If so why is it required? Dont you think the this condition is always true once the tree is traversed completely?

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

``````bool balanced_tree(root){
if(root ==NULL){
return true;
}
int lh = height(tree->left);
int rh = height(tree->right);
if(abs(lh-rh)<=1){
return balanced_tree(tree->left)&&balanced_tree(tree->right);
}else{
return false;
}
}``````

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

see here height of the tree would be calculated multiple times for the same set of nodes

so the time complexity become O(n^2)

we need to use the fact that to calculate the height of a tree we are calculating height of subtree and so there should not be need to again calculate height of sub tree which would done in this case when you are doing
balanced_tree(tree->left)&&balanced_tree(tree->right)

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

@student: then each should contain additional variable 'height'..

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

@cobra : yeah exactly we just need to pass the height ....

it would be O(1) extra space in each recursion call ...

check my implementation below.... have submitted it ...

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

``````public bool IsBalanced(Node root)
{
return Max(root) - Min(root) <= 1;
}

private int Max(Node root)
{
if (root == null) return 0;

return 1 + Math.Max(Max(root.Left), Max(root.Right));
}

private int Mini(Node root)
{
if (root == null) return 0;

return 1 + Math.Mini(Mini(root.Left), Mini(root.Right));
}``````

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

``````Mini() function is wrong... try for the data 4 3 2 1

4
\
3
\
2
\
1``````

here the min depth is 4, but your logic returns 1

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

Why? Depth must be calculated by comparing left/right leaf?
When there's no leaf, as it counts root as +1, I rather think it's correct behaviour.

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

your code is just checking the height of the left of the root and right of the root.. not checking whether each and every node of the tree are balanced..

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

I posted to wrong place... Sorry for the mess...

My code recirsively calls max and min to traverse each and every node.

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

``````1
/  \
2    3
/       \
4         5
/            \
6             7``````

is the tree not balanced according to your code ?

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

Balanced apparently.

My code is exactly same as airfang613's code

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

ya Baka, your code is right...

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

What is the definition of balanced?

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

What? Didn't you notice it calls min and max method recirsively for each and every node?

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

What? Didn't you notice it calls min and max method recirsively for each and every node?

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

``````bool is_tree_height_balanced(TreeNode* root, int& h)
{
if (root == NULL) return true;
int left_height(0), right_height(0);
bool lans = is_tree_height_balanced(root->left, left_height);
bool rans = is_tree_height_balanced(root->right, right_height);
h = 1 + max(left_height, right_height);
return abs(left_height - right_height) <=1 && lans && rans;

}``````

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

At each node check the balanced property, and quit when found a node that does not satisfy it.

``````bool isBalanced(Node *node, int &height) {
int hleft, hright;
bool lBal, rBal;
if (!node) {
height=0
return true;
}

lBal=isBalanced(node->left, hleft);
if (!lBal) return false;

rBal=isBalanced(node->right, hright);
if (!rBal) return false;

height=max(hleft,hright);
return true;
}``````

Time complexity: O(N)
Space complexity: O(N)

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

Find height -

``````unsigned int height(node *root)
{
if( root )
{
return 1+max( height(root->left), height(root->right));
}
return 0;
}``````

Find height of left and right subtrees and check difference

``````int is_balanced( node *root)
{
unsigned int diff = 0;
if( root )
{
unsigned int lh = height(root->left);
unsigned int rh = height(root->right);
if( lh > rh )
diff = lh-rh;
else
diff = rh-lh;
}
if( diff > 2 )
return 0;
return 1;
}``````

Tree is unbalanced if difference of left and right subtrees exceed 2

Comment hidden because of low score. Click to expand.
-1
of 1 vote

sorry that was tree

``````bool balanced_tree(tree){
if(tree ==NULL){
return true;
}
int lh = height(tree->left);
int rh = height(tree->right);
if(abs(lh-rh)<=1){
return balanced_tree(tree->left)&&balanced_tree(tree->right);
}else{
return false;
}
}``````

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.