Check Binary Tree is balanced or not

/***
4.1 Implement a function to check if a binary tree is balanced. For the purposes of
this question, a balanced tree is defined to be a tree such that the heights of the 
two subtrees of any node never differ by more than one.
***/

#include<iostream>

using namespace std;

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

bool isBalanced(node *root) {
if(getheight(root) != -1)
return true;
else false;
}

int getheight(node *n) {
int d;
if(n->left == nullptr || n->right == nullptr) {
return 0;
}

if(getheight(n->left) == -1 || getheight(n->right) == -1)
return -1;
d = getheight(n->left) - getheight(n->right);

if(d > 1 || d < -1) return -1;
else return max(getheight(n->left), getheight(n->right)) + 1;
}

Comments

Popular posts from this blog

Sudoku

Longest prefix matching - trie

Climbing Stairs