Problem Statement
Given a binary tree, determine if is height-balanced.
Height-Balanced: A binary tree is said to be height-balanced if the left and right subtrees of every node differ in height by no more than 1.
Sample Test Cases :
Input 1:
Output 1:
True
Explanation 1:
For every node in the tree, the height of the left and right subtree for that node differs by at most 1.
Input 2:
Output 2:
False
Explanation 2:
For node 1, the difference between the heights of the left and right subtree exceeds 1.
Approach 1: Naive
We can solve this problem naively by using a recursive approach. The approach is as follows:
- For each node, calculate the heights of the left and right subtrees of that node.
- If the difference between heights is greater than 1, return false.
- Else recursively check if the left and right nodes of the original node are also height-balanced.
Code / Implementation:
C++ Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int depth(TreeNode * root) {
if (root == NULL) {
return 0;
}
return max(depth(root -> left), depth(root -> right)) + 1;
}
bool isBalanced(TreeNode * root) {
if (root == NULL) {
return true;
}
int leftHeight = depth(root -> left);
int rightHeight = depth(root -> right);
if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root -> left) && isBalanced(root -> right)) {
return true;
} else {
return false;
}
}
};
Java Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(depth(root.left), depth(root.right)) + 1;
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeight = depth(root.left);
int rightHeight = depth(root.right);
if (Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
return true;
} else {
return false;
}
}
}
Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def depth(self, root):
if root is None:
return 0
else:
return max(self.depth(root.left), self.depth(root.right)) + 1
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
leftHeight = self.depth(root.left)
rightHeight = self.depth(root.right)
if (
abs(leftHeight - rightHeight) <= 1
and self.isBalanced(root.left)
and self.isBalanced(root.right)
):
return True
else:
return False
Complexity Analysis:
- Time Complexity: O(n * n)
- Space Complexity: O(1)
Approach 2: Optimal
The optimal approach is the same as the naive approach, but we can optimize the complexity by calculating the height of the subtrees of each node, in the same recursive function call, rather than calling a separate function to calculate the height of subtrees for each node.
Since the recursion progresses in a bottom-up manner, the heights of the subtree of the children can be used to compute the heights of the subtree of the current node using the relation,
- Height of current node = max(height of left subtree, height of right subtree) + 1.
Code Implementation:
C++ Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int check(TreeNode * root, bool & isBalanced) {
if (root == NULL) {
return 0;
}
int leftDepth = check(root -> left, isBalanced);
int rightDepth = check(root -> right, isBalanced);
if (abs(leftDepth - rightDepth) > 1) {
isBalanced = false;
}
return max(leftDepth, rightDepth) + 1;
}
bool isBalanced(TreeNode * root) {
bool bal = true;
check(root, bal);
return bal;
}
};
Java Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean isBalanced = false;
public int check(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = check(root.left);
int rightDepth = check(root.right);
if (Math.abs(leftDepth - rightDepth) > 1) {
isBalanced = false;
}
return Math.max(leftDepth, rightDepth) + 1;
}
public boolean isBalanced(TreeNode root) {
isBalanced = true;
check(root);
return isBalanced;
}
}
Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def check(self, root, isBalanced):
if root is None:
return 0
leftDepth = self.check(root.left, isBalanced)
rightDepth = self.check(root.right, isBalanced)
if abs(leftDepth - rightDepth) > 1:
self.isBalanced[0] = False
return max(leftDepth, rightDepth) + 1
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.isBalanced = [True]
self.check(root, self.isBalanced)
return self.isBalanced[0]
Complexity Analysis:
- Time Complexity: O(n)
- Space Complexity: O(1)
Practice Problem:
FAQs
Q.1: In what other types of trees is the concept of balancing used?
Ans: AVL Trees, Red-Black Trees, Splay Trees, etc are a few examples of trees where the concept of self-balancing is used.
Q.2: What is the time complexity of the depth function in the naive approach?
Ans: The depth function in the naive approach works in O(n).
