Problem: You have been given a binary tree check if it is a balanced binary tree.
A Binary tree is said to be balanced if the difference of leftsubtree and rightsubtree do not exceed 1. Here in this question, you need to return true if it is balanced otherwise false.
Example 1:
Input: root = [1, 2, 5, 3, 4]
Output: true
Example 2:
Input: root = [1, 2, null, 4]
Output: false
Approach:
In this approach we will try to calculate the height of leftSubTree as well as RightSubTree for each node and then we will calculate the height difference for current node. If we get height difference greater than 1 we will return -1 else we will continue for calculating height difference for other tree nodes. Here -1 indicates that the tree is not balanced.
Code Implementation:
public class isBalancedTree {
static class Node {
int data;
Node left, right;
Node(int key) {
data = key;
left = right = null;
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(5);
root.left.left = new Node(3);
root.left.right = new Node(4);
// Passing root node to isBalanced method
if (isBalanced(root) == -1) {
System.out.println("false");
} else {
System.out.println("true");
}
}
public static int isBalanced(Node root) {
// if root is null return 0
if (root == null)
return 0;
// getting height of leftSubTree
int lh = isBalanced(root.left);
// getting height of rightSubTree
int rh = isBalanced(root.right);
// calculating height difference of current node
int heightDifference = Math.abs(lh - rh);
// if heightDifference is greater than 1 return -1
if (heightDifference > 1)
return -1;
/*
* if either from leftSubTree or rightSubTree we get -1 it means tree is not
* balanced hence return -1
*/
if (lh == -1 || rh == -1)
return -1;
// return maximum height of current node
return Math.max(lh, rh) + 1;
}
}
Output:
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).
