Balanced Binary Tree Problem
Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example 1:
3
/ \
9 20
/ \
15 7
Return true.Example 2:
1
/ \
2 2
/ \
3 3
/ \
4 4
Return false.Balanced Binary Tree Solution in Java
A binary tree is balanced if, for every node -
- The left subtree is balanced,
- The right subtree is balanced, and
- The difference between the height of the left subtree and the height of the right subtree is less than or equal to 1.
To solve the problem, We can start from the root node of the tree, check if the difference between the height of the left subtree and the height of the right subtree is less than or equal to 1, and then recurse to find out if the left subtree is balanced and the right subtree is balanced:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class BalancedBinaryTree {
private static int height(TreeNode node) {
if(node == null) {
return 0;
}
return Math.max(height(node.left), height(node.right)) + 1;
}
private static boolean isBalanced(TreeNode node) {
if(node == null) {
return true;
}
return Math.abs(height(node.left) - height(node.right)) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(isBalanced(root));
}
}The above solution can be optimized by calculating the height and the isBalanced properties in the same recursion:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class HeightBalancedPair {
int height;
boolean balanced;
HeightBalancedPair(int height, boolean balanced) {
this.height = height;
this.balanced = balanced;
}
}
class BalancedBinaryTree {
private static HeightBalancedPair getHeightBalancedPair(TreeNode node) {
if(node == null) {
return new HeightBalancedPair(0, true);
}
HeightBalancedPair leftSubtree = getHeightBalancedPair(node.left);
HeightBalancedPair rightSubtree = getHeightBalancedPair(node.right);
int height = Math.max(leftSubtree.height, rightSubtree.height) + 1;
boolean balanced = Math.abs(leftSubtree.height - rightSubtree.height) < 2 &&
leftSubtree.balanced &&
rightSubtree.balanced;
return new HeightBalancedPair(height, balanced);
}
public static boolean isBalanced(TreeNode root) {
return getHeightBalancedPair(root).balanced;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
System.out.println(isBalanced(root));
}
}