1
\$\begingroup\$
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)...

\$\endgroup\$
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – tobias_k Jul 5 '13 at 11:23
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.