To check if a binary tree is balanced or not we need to check if both its left and right children are balance and difference between their heights is atmost 1. Here instead of computing the height for each node multiple times we can store the height in a hashmap i.e for each node its corresponding height. We can even store the height of a node as a property in the node itself. rest of the code is straight forward.
/**
* Definition for a binary tree node.
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
// first we will get the left height and right height of the node
// and compute the height difference.if it is > 1 we will return false
// hashtable to maintain height of each node to reduce the no of redundant
// height computations
static Hashtable<TreeNode, Integer> haTab = new Hashtable<>();
public static boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
int leftHeight, rightHeight;
leftHeight = height(root.left);
rightHeight = height(root.right);
// if left child and right child are balanced and the difference in
// their heights is < 2
// then it is balanced
if (isBalanced(root.left) && isBalanced(root.right)
&& Math.abs(leftHeight - rightHeight) < 2) {
return true;
}
return false;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(-2);
root.right = new TreeNode(-3);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(-1);
System.out.println(isBalanced(root));
}