Complexity Of Determining Tree is balanced?

boolean isBalance(Node root) {
if (root == null )
return true;
return Math.abs(getHeight(root.left)-getHeight(root.right)) <=1;
}

int getHeight(Node N) {
int L = 0;
int R = 0;
if (N.L!=null) L = getHeight(N.L);
if (N.R!=null) R = getHeight(N.R);
return 1 + Max(L,R);
}


I believe that the run time of my algorithm is O(N); But one of my friend told this runs for O(N^2);

My question is whether I am wrong or right since I believe I visit each node once. SO for that its O(N)...

• Note that isBalanced will return true if the height of the two branches is (near) equal even if the branches themselves are not balanced. Is this intentional? – tobias_k Jul 5 '13 at 11:23

Your getHeight method could be simpler (and more correct) if it was handling the null case.
int getHeight(Node N) {