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\$
1
  • 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
    Commented Jul 5, 2013 at 11:23

1 Answer 1

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 and acknowledge you have read our privacy policy.

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