CareerCup

Find the max depth and min depth. The difference between these two numbers shouldn't be more than 1.

Do a DFS. Whenever we are backtracking in the DFS maintain the node's height. So we'll encounter a leaf and note it's height as 1 then we go to it's parent do a DFS from there again noting the height it's right child. While backtracking to it's parent we know if the height of the two subtrees, so check if the property is held, if no report, if yes note the height again and continue.

Koha - How will you compute the max and min depth? What would be the cost of each?

Use breadth first traverse starting from the root. Put {node, distance from root} into queue during traverse. Remember the max and min distance for leaves only. In the end, if max-min>1, the tree is not balanced. The time is 0(N) and the space is 0(N)

int computeHeight(NODE* pNode)
{
if(!pNode)
return -1;
int heightLeft = computeHeight(pNode->pLeft);
int heightRight = computeHeight(pNode->pRight);
int heightNode = 1 + ((heightLeft > heightRight) ? heightLeft : heightRight);
return heightNode;
}

bool isBalanced(NODE* pNode)
{
if(!pNode)
return true;
if(!isBalanced(pNode->pLeft))
return false;
if(!isBalanced(pNode->pRight))
return false;
int heightLeft = computeHeight(pNode->pLeft);
int heightRight = computeHeight(pNode->pRight);
int heightDiff = heightLeft - heightRight;
if((heightDiff != 0) && (heightDiff != 1) && (heightDiff != -1))
return false;
return true;
}

Code for the khoa's solution

int maxDeptth(node *node){
	if(node == NULL) return 0;
	else
		return(MAX(maxDepth(node->left),maxDepth(node->right))+1);
}

int minDepth(node *node){
	if(node == NULL) return 0;
		else
		return(MIN(maxDepth(node->left),maxDepth(node->right))+1);
}

bool IsBalanced(node * node){
	return (maxDepth(node) - minDepth(node) >1)
	
}

Here's a recursive solution:

bool isBalanced(Node* r)
{
if (r->left && r->right)
{
bool a = isBalanced(r->left);
bool b = isBalanced(r->right);

if (a && b)
return true;
return false;
}

if (r->left)
{
if (!r->left->left && !r->left->right)
return true;
return false;
}

if (r->right)
{
if (!r->right->left && !r->right->right)
return true;
return false;
}

return true;
}

bool IsBalanced(node *root)
{

if(root == NULL)
return true;

if(!IsBalanced(root->left))
return false;

if(!IsBalanced(root->right))
return false;

int heightL = root->Left?root->left->height:0;
int heightR = root->Right?root->Right->height:0;

if(abs(heightL - heightR) > 1)
return false;

root->height = max(heightL,heightR) + 1;
return true;
}

bool isBalancedInternal(node* root,int depth,int* maxDepth)
{
if (!root)
{
return true;
}
if (root->left == NULL && root->right == NULL)
{
if ( abs( depth - (*maxDepth) ) > 1)
{
return false;
}
if ( depth > *maxDepth)
{
*maxDepth = depth;
return true;
}
}

return (isBalancedInternal(root->left,depth + 1,maxDepth) &&
isBalancedInternal(root->right,depth + 1,maxDepth));

}
bool isBalanced(node* root)
{

int maxDepth = 0;
return isBalancedInternal(root,0,&maxDepth);
}

@Vamsi

Your code has an error basically design issue.You are not checking if the left or the right subtrees are balanced.Maybe the left subtree is unbalanced but the heights of both the subtrees maybe same.Suppose, left subtree has leaf nodes at level 3 and 7,then height of left subtree would be 7.Lets say the height of the right subtree be 7 as well.So your code will give me that the tree is balanced as the heights of both the subtrees are same.But the answer is false.The tree is not balanced!!...see the loop hole in your code !!

Hi Lost I am afraid you did not really understand what Vamsi is doing. in your example, if there is a leaf node at 3 and 7, then the max depth will be>=7 and the minimum depth will be <=3, and the difference is >=4, then it is not balanced. it does not only look at the height different between left and right subtree, it checks the difference between the leaf with the minimum and maximum depth, thus the solution is correct

I think Vamsi's solution has a problem with the minDepth implementation.
I think it should be
int minDepth(Tree* root)
{
if(!root) return 0;
if(!root->left||!root->right) return 0;
return(1+min(minDepth(root->left),minDepth(root->right));
}

sorry some modification
int mindDepth(Tree* root)
{
if(!root) return -1;
if(!root->left||!root->right) return 0;
return(1+min(minDepth(root->left),minDepth(root->right));
}

khexa's solution is not correct

bool IsBalanced(node* root)
{
if(!root) return false;
int level=0, max=MIN_INT; min=MAX_INT;
DoIsBalanced(root,level,&max,&min);
if(max-min>1) return false;
return true;
}

DoIsBalance(node* root,int level,int max,int min)
{
if(!root)
{
if(level>max) max=level;
if(level<min) min=level;
return;
}
DoIsBalance(root->left,level+1,max,min);
DoIsBalance(root->right,level+1,max,min);
}