Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, 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.

To check whether a tree is balanced, we will check from the root, the height of the left child and the height of the right child and perform the process recursively. The height of a node can be calculated recursively in a separate function. However, we do not want so many recursions. What should we do? We can check the balance with the height at the same time. If the difference of the height from the left sub-tree to the right sub-tree is greater than 1, then we just return an error code -1, and do not need to do a further check.

01 public boolean isBalanced(TreeNode root) {
02     if(checkHeight(root)==-1)
03         return false;
04     return true;
05 }
06 
07 public int checkHeight(TreeNode root)
08 {
09     if(root==null)
10         return 0;
11     int leftHeight=checkHeight(root.left);
12     if(leftHeight==-1)
13         return -1;
14     int rightHeight=checkHeight(root.right);
15     if(rightHeight==-1)
16         return -1;
17     if(rightHeight-leftHeight>1 || rightHeight-leftHeight <-1)
18         return -1;
19     else
20     {
21         return findMax(leftHeight,rightHeight)+1;
22     }
23   
24 }
25 public int findMax(int a,int b)
26 {
27     return a>b?a:b;
28 }