PROBLEM DESCRIPTION
A binary tree is balanced if for each node in the tree, the difference between the height of its LST and RST is at most 1.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int heightBalancedBinaryTreeX(BinaryTree tree) {
if(tree == null) return 0;
int left = heightBalancedBinaryTreeX(tree.left);
int right = heightBalancedBinaryTreeX(tree.right);
return 1 + Math.max(left, right);
}
public boolean heightBalancedBinaryTree(BinaryTree tree) {
if(tree == null) return true;
int left = heightBalancedBinaryTreeX(tree.left);
int right = heightBalancedBinaryTreeX(tree.right);
return Math.abs(left-right) <= 1 && heightBalancedBinaryTree(tree.left) && heightBalancedBinaryTree(tree.right);
}