Check if tree is balanced in O(n) time

Check if tree is balanced in O(n) time

  October 20, 2017    

---

Idea is to use map and store height of each subtree but here we will take O(2n) time.

1 for saving 
2 for checking for balance

For only O(n) we will simultaneously check for height and balance factor

Code:

 boolean isBalanced(Node root,height o)
    {
if(root==null)
{
    o.h=0;
    return true;
}
height x=new height(),y=new height();
boolean l=isBalanced(root.left,x);
boolean r=isBalanced(root.right,y);
o.h=((x.h>y.h)?x.h:y.h)+1;
if(Math.abs(x.h-y.h)>1)
return false;
return l&r;
    }
    boolean isBalanced(Node root)
    {
        Integer t;
return isBalanced(root,new height());
    }