Return statement not working correctly from loop

Question

I'm working on a project involving balancing binary trees and I'm having a bit of an issue.

For a portion of my project, I want to look at a tree (or subtree) and compare the maximum lengths of said subtrees left child's paths and right child's paths. If the absolute difference between the maximum lengths of these paths is greater than 1, I want to return the first node found having this property. The logic is somewhat simple.. for example if I had the tree:

My algorithm would look at 64 and compare the lengths of the paths going down the left and right side (5 & 4 respectively). This doesn't create a flag since the difference is 1. Then I would recursively look at 64's children. First It would look at 43, then go to 26. After 26 (since each of its children has length 1 to the leaf) the algorithm would move onto 62. At this point a flag will be thrown, as 62s left path has a length of 3 and it doesn't have a right path. This is where I want to exit my loop and return 62. However, my loop continues to keep running until it checks the final nodes.

As you can see, the algorithm continues to run and returns a null node rather than the node I wanted. I'm not sure why it does this but I think it has something to do with precedence and scope. The code for the specific algorithm is as follows:

    public BinaryNode<Integer> NodeCheck(BinaryNode<Integer> Node) throws IllegalStateException
    {
        System.out.println("CHECKING NODE: " + Node.getData());

        int leftHeight = 0;
        int rightHeight = 0;

        if (Node.hasLeft())
        {
            leftHeight = 1 + findHeight(Node.getLeft());
        }

        if (Node.hasRight())
        {
            rightHeight = 1 + findHeight(Node.getRight());
        }
        System.out.println("LEFT HEIGHT = " + leftHeight);
        System.out.println("RIGHT HEIGHT = " + rightHeight);

        int z = Math.abs(leftHeight - rightHeight);
        if (z > 1)
        {
            System.out.println();
            System.out.println();
            System.out.println("PROBLEM DETECTED AT NODE " + Node.getData() + " ATTEMPTING TO RETURN NODE");
            BinaryNode<Integer> flag = createNode(Node.getData(), Node.getParent(),Node.getLeft(), Node.getRight());

            return flag;
        }

        for (BinaryNode<Integer> c : children(Node))
            {
                if (findHeight(c) > 1 && z<= 1)
                    {NodeCheck(c);}
            }


        return createNode(0,null,null,null);

    }

I think its important to note that I end up processing the information within the if (z > 1) statement because the System.out.println() statements are executed, which leads me to believe that the return statement is executed. However, this doesn't exit the function as I would have assumed.

Answer 1

I think your problem is coming from where you call the NodeCheck() in the for loop. I assume that when you said if (findHeight(c) > 1 && z <=1) you meant to say "if the child node has a height greater than 1 and 'z' has not yet been found to be greater than 1, then check the said child node".

However, when you run it the first time (on the root), if at that point z <= 1 (which it is in the example you've given), it will then call NodeCheck() on the children of that root (namely 43 and 92). So even if it finds a node with z > 1 down the left, the same check will already have been requested down to the right, which is why it doesn't stop when the left returns.

Here's an alternative to that for loop: you could go down one way and wait to see if anything was found down that path before going the other. Your code becomes

public BinaryNode<Integer> NodeCheck(BinaryNode<Integer> Node) throws IllegalStateException
{
    System.out.println("CHECKING NODE: " + Node.getData());

    int leftHeight = 0;
    int rightHeight = 0;

    if (Node.hasLeft())
    {
        leftHeight = 1 + findHeight(Node.getLeft());
    }

    if (Node.hasRight())
    {
        rightHeight = 1 + findHeight(Node.getRight());
    }
    System.out.println("LEFT HEIGHT = " + leftHeight);
    System.out.println("RIGHT HEIGHT = " + rightHeight);

    int z = Math.abs(leftHeight - rightHeight);
    if (z > 1)
    {
        System.out.println();
        System.out.println();
        System.out.println("PROBLEM DETECTED AT NODE " + Node.getData() + " ATTEMPTING TO RETURN NODE");
        BinaryNode<Integer> flag = createNode(Node.getData(), Node.getParent(),Node.getLeft(), Node.getRight());

        return flag;
    }

    /*EDIT STARTS HERE*/

    if (Node.hasLeft() && findHeight(Node.getLeft()) > 1) //Check in the left node and see if it returns a flag
    {
        BinaryNode<Integer> left = Node.getLeft();
        BinaryNode<Integer> result = CheckNode(left);

        //If 'result' is null, then there was no flag, otherwise it found a flag. So check for that
        if (result != null)
        //If this condition is met, then result is a flag and the left child
        //found a z > 1. So cut the operations here and just return the same
        //flag to the one who called 'CheckNode()' on this 'Node'. 
        {return result;}
    }

    if (Node.hasRight() && findHeight(Node.getRight()) > 1) //Check in the right node and see if it returns a flag
    {
        BinaryNode<Integer> right = Node.getRight();
        BinaryNode<Integer> result = CheckNode(right);

        //Same as above
        if (result != null)
        //If this condition is met, then result is a flag and the right
        //child found a z > 1. So cut the operations here and just return
        //the same flag to the one who called 'CheckNode()' on this 'Node'. 
        {return result;}
    }

    /*EDIT ENDS HERE*/

    return null;

}

Note that by the time you call CheckNode() on children you don't need to check that z <= 1 because if z was greater than 1, it would have returned and exited in the block where you check for the flag and do the System.out.println() stuff.

It looks easier to return null at the end, so that you know right away from just looking at the returned value if it found a flag (will be a BindaryNode object) or not (will be null).

Answer 2

The problem is, that you call this method recursively, but without a check.

You should change the followings to make it work:

• The final return should return null.
• In the loop just before that you should check the returned value, and if it is not null return it.

So this last part of your method should look something like this:

    for ( final BinaryNode<Integer> c : children( node ) )
    {
        if ( findHeight( c ) > 1 && z <= 1 )
        {
            final BinaryNode<Integer> res = nodeCheck( c );
            if ( null != res )
                return res;
        }
    }
    return null;
}

Running it produces this output:

CHECKING NODE: 64
LEFT HEIGHT = 5
RIGHT HEIGHT = 4
CHECKING NODE: 43
LEFT HEIGHT = 3
RIGHT HEIGHT = 4
CHECKING NODE: 26
LEFT HEIGHT = 2
RIGHT HEIGHT = 2
CHECKING NODE: 62
LEFT HEIGHT = 3
RIGHT HEIGHT = 0


PROBLEM DETECTED AT NODE 62 ATTEMPTING TO RETURN NODE