CareerCup

check the hieght at each node recursively.

<pre lang="" line="1" title="CodeMonkey26395" class="run-this">struct node{
int n;
node *left, *right;
};
node *root = NULL;

node *newnode(int n){
node *np = new node;
np->n = n;
np->left = np->right = NULL;
return np;
}

void insert(node *&root, node *np){
if(root == NULL) root = np;
else if(np->n < root->n) insert(root->left, np);
else insert(root->right, np);
}

int height(node *n){
if(n == NULL) return 0;
return max( height(n->left), height(n->right) ) + 1;
}

bool isBalanced(node *n){
if(n == NULL) return true;

if(abs(height(n->left) - height(n->right)) > 1) return false;
return isBalanced(n->left) && isBalanced(n->right);
}

void inorder(node *n){
if(n == NULL) return;
inorder(n->left);
cout<<n->n<<" ";
inorder(n->right);
}



int main(){
//int a[] = {5,2,4,7,8,2,4,67,9,2,3,56}, n = 12;
int a[] = {5, 3, 4, 2, 1, 8, 10, 6, 9}, n = 9;
cout<<"Input Numbers: \n";

for(int i=0; i<n; i++) insert(root, newnode(a[i]));

cout<<"Inorder: "<<endl;
inorder(root); cout<<endl;

cout<<"Height: "<<height(root)<<endl;
cout<<"Is Balanced: "<<isBalanced(root)<<endl;
return 0;
}
</pre><pre title="CodeMonkey26395" input="yes">{5, 3, 4, 2, 1, 8, 10, 6, 9} -> balanced tree
{5,2,4,7,8,2,4,67,9,2,3,56} -> unbalanced tree
</pre>

if(abs(height(n->left) - height(n->right)) > 1) return false;

Is this correct .
I think
the condition should be >=1 or >0

if(abs(height(n->left) - height(n->right)) > 0) return false;

Doesn't matter whether BST or BT...above solutions work for both.

The most efficient would be

int isBalanced(node *n)
{
if(n == NULL) return -1;
int lh = isBalanced(n->l);
int rh = isBalanced(n->r);

if(lh == -2 || rh == -2) return -2;


if(abs(lh - rh) > 1) return -2;
return max(lh, rh ) + 1;
}
as takes only O(n).

I think the key is knowing the definition of a what it means to be a balanced tree (different than a complete tree).

Difference between max depth and min depth <=1

I believe we do two depth first searches (dfs) to find the min depth in O(log(n)) and the max depth in O(log(n)), compare the two and we are done!

Hopefully this helps.

Good luck in finding the job of your dreams!

One more thing.. For non Binary Trees the principle still holds, the only difference is you have a set of nodes, rather than just the left and right.

static void bbtree::height(node **n) {
if ((n->lc != NULL) || (n->rc != NULL)) {
return 0;
}
else {
int l1 = height(n->lc);
int l2 = height(n->rc);
if (l1>l2) { return l1; }
else { return l2; }
}

int bbtree::isbalanced() {
if (abs(height(root->lc) - height(root->rc))>1) {
return 0;
}
else { return 1; }
}

I think instead of performing DFS twice, we could go for Breadth first traversal once and while doing a breadth first search, the first node that is encountered without any child node can be stored as that with minimum height and the last node that is encountered without any child can be stored as the one with max height.

So just with two variables and a BF traversal, we can find whether a tree is balanced or not by the difference of these variables.

If > 1 then not balanced, else balanced.

BLS reporting....
ever heard of AVL trees? use em....

For a tree to be balance, following conditions must hold true.
1. Left sub tree should be balanced
2. Right sub tree should be balanced
3. absolute difference between the heights of the two subtrees should be at most 1.
A recursive solution can be framed using the above mentioned conditions and can be done in O(n)

calculate the maximum number of data in a B-TREE of order 5 with the height of 3