Complexity Of Determining Tree is balanced? boolean isBalance(Node root) {
    if (root == null ) 
        return true;
    return Math.abs(getHeight(root.left)-getHeight(root.right)) &lt;=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)...
Your getHeight method could be simpler (and more correct) if it was handling the null case.

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


Also, I think you should have a read at this quite similar question.