In the balanced binary tree problem, we have given the root of a binary tree. We have to determine whether or not it is height balance.
Table of Contents
Examples
Input
Output
true
Input
Output:
false
Balanced Binary Tree
Every node in a balanced binary tree has a difference of 1 or less between its left and right subtree height. An empty tree always follows height balance.
That is, for a balanced binary tree,
-1 <= Height of left subtree – Height of right subtree <= 1
Naive Approach for Balanced Binary Tree
For every node to calculate the height of its left and right subtree, if the difference is greater than 1, return false, else recur for its left and right subtree and return true if both are balanced, in all other cases return false.
Base Case: Empty tree follows height balance.
- Start from the root. If the root is null, return true.
- Calculate the height of its left and right subtree and store them in variables named leftHeight and rightHeight respectively.
- Recursively call the balance height function for root’s left and right subtree. If both left and right subtree are balanced and the difference between the leftHeight and rightHeight is less than or equals to 1, return true, else return false.
Time Complexity = O(n^2)
JAVA Code
public class BalancedBinaryTree {
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
// Function to calculate height of a tree rooted at root
private static int height(Node root) {
if (root == null) {
// Height of empty tree is 0
return 0;
}
// Height of tree is 1 + maximum of height of left or right subtree
return 1 + Math.max(height(root.left), height(root.right));
}
// Function to check if given tree is balanced or not
private static boolean isBalanced(Node root) {
if (root == null) {
// Empty tree is always balanced
return true;
}
// Find the left subtree height and right subtree height
int leftHeight = height(root.left);
int rightHeight = height(root.right);
// If this node is balanced and also its left and right subtree are balanced return true
// else return false
return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
&& isBalanced(root.right);
}
public static void main(String[] args) {
// Tree in example 1
Node root = new Node(18);
root.left = new Node(4);
root.right = new Node(20);
root.right.left = new Node(13);
root.right.right = new Node(70);
System.out.println(isBalanced(root));
// Tree in example 2
Node root2 = new Node(3);
root2.left = new Node(4);
root2.right = new Node(8);
root2.left.left = new Node(5);
root2.left.right = new Node(9);
root2.right.right = new Node(7);
root2.right.right.left = new Node(6);
System.out.println(isBalanced(root2));
}
}C++ Code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
};
// Function to calculate height of a tree rooted at root
int height(Node *root) {
if (root == NULL) {
// Height of empty tree is 0
return 0;
}
// Height of tree is 1 + maximum of height of left or right subtree
return 1 + std::max(height(root->left), height(root->right));
}
// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
if (root == NULL) {
// Empty tree is always balanced
return true;
}
// Find the left subtree height and right subtree height
int leftHeight = height(root->left);
int rightHeight = height(root->right);
// If this node is balanced and also its left and right subtree are alanced return true
// else return false
return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
&& isBalanced(root->right);
}
// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main() {
// Tree in example 1
Node *root = newNode(18);
root->left = newNode(4);
root->right = newNode(20);
root->right->left = newNode(13);
root->right->right = newNode(70);
if (isBalanced(root) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Tree in example 2
Node* root2 = newNode(3);
root2->left = newNode(4);
root2->right = newNode(8);
root2->left->left = newNode(5);
root2->left->right = newNode(9);
root2->right->right = newNode(7);
root2->right->right->left = newNode(6);
if (isBalanced(root2) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true false
Optimized Approach for Balanced Binary Tree
Modify the height function to return the height of the tree if the tree is satisfied height balance properties else return -1.
- The empty tree is always followed height balance(Base Case).
- Find the left height by calling the height function recursively, if the height is -1, the left subtree is unbalanced, return -1 immediately.
- Find the right height by calling the height function recursively, if the height is -1, the right subtree is unbalanced return -1 immediately.
- If the difference between left and right height is less than or equals to 1, return the height(1 + max(leftHeight, rightHeight), else return -1.
Time Complexity = O(n)
JAVA Code
public class BalancedBinaryTree {
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
// Modified height function
// Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
private static int height(Node root) {
if (root == null) {
// Empty tree is always balanced
return 0;
}
// Find the left height
int lh = height(root.left);
if (lh == -1) {
// Left subtree is unbalanced
return -1;
}
// Find the right height
int rh = height(root.right);
if (rh == -1) {
// Right subtree is unbalanced
return -1;
}
if (Math.abs(lh - rh) <= 1) {
// Balanced tree, return the height
return Math.max(lh, rh) + 1;
}
// Unbalanced tree
return -1;
}
private static boolean isBalanced(Node root) {
// Call the modified height function
int height = height(root);
if (height == -1) {
// Unbalanced tree
return false;
}
// Balanced tree
return true;
}
public static void main(String[] args) {
// Tree in example 1
Node root = new Node(18);
root.left = new Node(4);
root.right = new Node(20);
root.right.left = new Node(13);
root.right.right = new Node(70);
System.out.println(isBalanced(root));
// Tree in example 2
Node root2 = new Node(3);
root2.left = new Node(4);
root2.right = new Node(8);
root2.left.left = new Node(5);
root2.left.right = new Node(9);
root2.right.right = new Node(7);
root2.right.right.left = new Node(6);
System.out.println(isBalanced(root2));
}
}C++ Code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
};
// Function to calculate height of a tree rooted at root
int height(Node *root) {
if (root == NULL) {
// Empty tree is always balanced
return 0;
}
// Find the left height
int lh = height(root->left);
if (lh == -1) {
// Left subtree is unbalanced
return -1;
}
// Find the right height
int rh = height(root->right);
if (rh == -1) {
// Right subtree is unbalanced
return -1;
}
if (abs(lh - rh) <= 1) {
// Balanced tree, return the height
return 1 + std::max(height(root->left), height(root->right));
}
// Unbalanced tree
return -1;
}
// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
// Call the modified height function
int h = height(root);
if (h == -1) {
// Unbalanced tree
return false;
}
// Balanced tree
return true;
}
// Function to allocate new memory to a tree node
Node* newNode(int data) {
Node *node = new Node();
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
int main() {
// Tree in example 1
Node *root = newNode(18);
root->left = newNode(4);
root->right = newNode(20);
root->right->left = newNode(13);
root->right->right = newNode(70);
if (isBalanced(root) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Tree in example 2
Node* root2 = newNode(3);
root2->left = newNode(4);
root2->right = newNode(8);
root2->left->left = newNode(5);
root2->left->right = newNode(9);
root2->right->right = newNode(7);
root2->right->right->left = newNode(6);
if (isBalanced(root2) == true) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}true false