4
\$\begingroup\$

I was writing this code to check if a tree is balanced or not and I ran into a situation where I would have liked the method to return 2 values at each step. First to signify whether the tree is balanced at that level or not, and second to return the height at the level so that I can use it to check the balanced nature of the parent. I ended up writing the method such that it returns -1 if the tree is not balanced and the actual height if the tree is balanced at that level.

Is there a better way to do it? If not, then I think I should at least have a better name for the method getHeight. Can you review my code as a whole and let me know my shortcomings?

public boolean isBalanced(Node root){
        return getHeight(root)!=-1;
    }

private int getHeight(Node node){
    if(node ==null)
        return 1;

    int leftHeight = getHeight(node.getLeft());
    int rightHeight = getHeight(node.getRight());
    if(leftHeight==-1 || rightHeight ==-1)
        return -1;

    int diff = Math.abs(leftHeight-rightHeight);
    if(diff>1)
        return -1;

    return Math.max(leftHeight,rightHeight) + 1;

}
\$\endgroup\$
6
  • \$\begingroup\$ stackoverflow.com/questions/8015630/… Is this your assumption of a balanced tree? \$\endgroup\$
    – chillworld
    May 13, 2015 at 6:53
  • \$\begingroup\$ Yeah. A tree is balanced if leftSubTree is balanced, rightSubTree is balanced and the difference in height between the left and right subtree is at most 1. \$\endgroup\$
    – maverick
    May 13, 2015 at 8:59
  • \$\begingroup\$ but each subTree should also be balanced. Do I understand the code not right or don't you check that? \$\endgroup\$
    – chillworld
    May 13, 2015 at 9:05
  • \$\begingroup\$ @chillworld If a subtree is imbalanced, then its height will be reported as -1. There are special-case checks for that. \$\endgroup\$ May 13, 2015 at 9:06
  • \$\begingroup\$ @200_success Oke, thx. Have a hard time with this code to see it without coding it. (Think the recursion is killing me here) \$\endgroup\$
    – chillworld
    May 13, 2015 at 9:36

2 Answers 2

3
\$\begingroup\$

These functions can be static, and therefore should be. Marking them static makes it clear that this is not object-oriented code. It also serves as a hint for the JIT to inline the helper function.

Instead of using Math.abs() and Math.max(), I suggest using Math.max() and Math.min(), which simplifies the conditionals a bit.

I would expect getHeight(null) to return 0. As you've written it, a node with no children is at height 2, which is a weird place to start counting, even if it works.

Never omit braces like that. You will contribute to a coding accident: [Citation 1] [Citation 2]. If you really want to omit braces, then put the entire conditional statement on the same line for safety.

private static int getHeight(Node node) {
    if (node == null) return 0;

    int leftHeight  = getHeight(node.getLeft()),
        rightHeight = getHeight(node.getRight());

    int taller  = Math.max(leftHeight, rightHeight),
        shorter = Math.min(leftHeight, rightHeight);

    if (shorter < 0 || taller - shorter > 1) {
        return -1;           // Unbalanced tree
    } else {
        return taller + 1;
    }
}
\$\endgroup\$
9
  • \$\begingroup\$ can you give reason why if the function can be static, it should be? i agree that for node == null the return shoul be zero \$\endgroup\$
    – Zavael
    May 13, 2015 at 8:15
  • 1
    \$\begingroup\$ I think you cannot omit the Math functions in that way, because the OP code assumes that the node is balanced only if the difference between left side and right side is greater than 1 (not equal to 0), therefore your code would skip this one case i think and return -1 \$\endgroup\$
    – Zavael
    May 13, 2015 at 8:29
  • 1
    \$\begingroup\$ @Zavael Oops, I was thinking of full trees, not balanced trees. Thanks! \$\endgroup\$ May 13, 2015 at 8:42
  • 1
    \$\begingroup\$ @Zavael static makes it clear that it's a pure function that has nothing to do with the state of the object — it won't be affected by it, and won't alter it. static also serves as a hint for the JIT to inline the function. \$\endgroup\$ May 13, 2015 at 8:45
  • \$\begingroup\$ yes, and therefore static has nothing in common with OOP, but with procedural programming, it just extracts and moves the code to another class, it does not decouple problem into objects whit their states and behaviours. It shoul be not ecplicitly suggested to replace it with static function. I dont agree that it has nothing to do with the state of object, it shows the state of object. Its out of scope of the OP question, but to backup my thoughts, if you have time please visit yegor256.com/2015/02/26/composable-decorators.html with the video to see what i mean \$\endgroup\$
    – Zavael
    May 13, 2015 at 8:57
0
\$\begingroup\$

If you dont reuse the getHeight(Node node) method for calculating the height, yes, you should rename it as it does not return the height for unbalanced tree and therefore the behaviour is unexpected. I would rename it to getBalancedHeight(Node node) for example.

After renaming you can even make the method public - it reports the state of the tree - its balanced height.

As was suggested by 200_success, fore node == null you should return 0 as height, as it makes more sense.

Otherwise the code looks good.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ How would you implement isBalanced() without getHeight()? \$\endgroup\$ May 13, 2015 at 10:41
  • \$\begingroup\$ @200_success yeah, thank you i realized the same think as you, that one node as child is acceptable :D \$\endgroup\$
    – Zavael
    May 13, 2015 at 13:05

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.