CareerCup

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

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

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
{
        
        if(*head == NULL)
                *head= newNode(data);
        else
        {
                if(data <= (*head)->data)
                        insert(&((*head)->left),data);
                else 
                        insert(&((*head)->right),data);
        }
        
}
 
int returnMax(int a, int b)
{
 
        return a>b?a : b;
}
 
int util_isBalanced(Node head,int *height)
{
        if(head == NULL)
        {
                *height = 0;
                return TRUE;
        }
        
        int leftHeight,rightHeight=0;
        int leftTree,rightTree;
        
        leftTree = util_isBalanced(head->left,&leftHeight);
        rightTree = util_isBalanced(head->right,&rightHeight);
 
        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 isBalanced(Node head)
{
        int height = 0;
        return util_isBalanced(head,&height);
}
 
int main()
{
        Node head = NULL;
        
        insert(&head,4);
        insert(&head,3);
        insert(&head,6);
        insert(&head,5);
        insert(&head,7);
        insert(&head,12);
        
        int isBalancedTree = isBalanced(head);
 
        isBalancedTree==TRUE?printf("Balanced") : printf("Not balanced");
        
        return 0;
}

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

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

What is the definition of balanced?

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

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

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; 

}

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)

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

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