java return statement

Question

Hi, I have a question about the following code

private void printTree(Node node){
    if(node==null) return;
    printTree(node.left);
    System.out.print(node.data+" ");
    printTree(node.right);
}

I don't really get the point of 'return;' statement there. It looks like if node is null, code returns nothing. but then without that line, a compiler generates an exception error.

Answer 1

This is a recursive function (one that calls itself repeatedly). The purpose of the return is to ensure that it doesn't attempt to do so forever, resulting in a null pointer exception as you run off the bottom of the tree.

What will happen is that the first time you call this function with a node (usually, but not always, the root node), it will first print out the left sub-tree of that node, then the value of the node itself, then the right sub-tree of that node.

The way it prints out the sub-trees is by calling itself with the top level node of that sub-tree. This is a very common method of elegantly processing recursive structures.

The test for null is so that it has a condition where the search down through the levels of the tree stops when it reaches a node that has no children on the particular side you're examining (left or right).

By way of example, let's say you have the following tree (uppercase letters with their numbers are real nodes with the numbers being their value, and === markers are nulls):

             A26                Level 0
              |
       +------+------+
       |             |
      B14           C84         Level 1
       |             |
    +--+--+       +--+--+
    |     |       |     |
   D11   ===     ===   E99      Level 2
    |                   |
 +--+--+             +--+--+
 |     |             |     |
===   ===           ===   ===   Level 3

Here's what will happen, when you call the function with A.

You call the function (level 0) with A.
  The function will call itself (level 1) with B (A left).
    The function will call itself (level 2) with D (B left).
      The function will call itself (level 3) with null (D left).
        The function will return to level 2.
      The function will print out 11 from D.
      The function will call itself (level 3) with null (D right).
        The function will return to level 2.
      The function will return to level 1.
    The function will print out 14 from B.
    The function will call itself (level 2) with null (B right).
      The function will return to level 1.
    The function will return to level 0.
  The function will print out 26 from A.
  The function will call itself (level 1) with C (A right).
    The function will call itself (level 2) with null (C left).
      The function will return to level 1.
    The function will print out 84 from C.
    The function will call itself (level 2) with E (C right).
      The function will call itself (level 3) with null (E left).
        The function will return to level 2.
      The function will print out 99 from E.
      The function will call itself (level 3) with null (E right).
        The function will return to level 2.
      The function will return to level 1.
    The function will return to level 0.
  The function will return to you.

The upshot is that it's printed out the sequence DBACE which, in a sorted tree, is the elements in sorted order (11, 14, 26, 84, 99).

---

Or a simpler version if you can't be bothered to read through my voluminous explanation above:

             A26                Level 0
              |
       +------+------+
       |             |
      B14           ===         Level 1
       |
    +--+--+
    |     |
   ===   ===                    Level 2

You call the function (level 0) with A.
  The function will call itself (level 1) with B (A left).
    The function will call itself (level 2) with null (B left).
      The function will return to level 1.
    The function will print out 14 from B.
    The function will call itself (level 2) with null (B right).
      The function will return to level 1.
    The function will return to level 0.
  The function will print out 26 from A.
  The function will call itself (level 1) with null (A right).
    The function will return to level 0.
  The function will return to you.

In that case, you'd get BA or (14,26).

Answer 2

Any method declared void doesn't return a value. It does not need to contain a return statement, but it may do so. In such a case, a return statement can be used to branch out of a control flow block and exit the method and is simply used like this:

return;

From Java LangSpec :

14.17 The return Statement

A return statement returns control to the invoker of a method (§8.4, §15.12) or constructor (§8.8, §15.9).

ReturnStatement:
        return Expressionopt ;

A return statement with no Expression must be contained in the body of a method that is declared, using the keyword void, not to return any value (§8.4), or in the body of a constructor (§8.8). A compile-time error occurs if a return statement appears within an instance initializer or a static initializer (§8.7). A return statement with no Expression attempts to transfer control to the invoker of the method or constructor that contains it. To be precise, a return statement with no Expression always completes abruptly, the reason being a return with no value.

A return statement with an Expression must be contained in a method declaration that is declared to return a value (§8.4) or a compile-time error occurs. The Expression must denote a variable or value of some type T, or a compile-time error occurs. The type T must be assignable (§5.2) to the declared result type of the method, or a compile-time error occurs.

Answer 3

It seems to me that if your node is null, it will get out of the function call before it throws a NullReferenceException. Because it is recursive, it needs it to deal with the nodes (leaves) of the tree by 'backing out' to its parent nodes.

Answer 4

You also have the return so that way you don't call node.data. Remember that if its null, you cannot call an instance method on it.

Answer 5

'return' statement here is acting as a terminating condition for the recursive call. Each recursive method requires a mendatory termination condition or else it goes in an infinite loop.

if(node==null) return;

this statement basically signifies that you have reached the leaf node (last node of the branch) and terminates any further movement of the cursor.

The exception that you are getting on removing return is due to the fact that you don't have any further nodes to move to once you have reached the leaf node and statements printTree(node.left); & printTree(node.right); are invalid.

Answer 6

A less confusing way to write this would be :

private void printTree(Node node){
    if (node.left != null) {
       printTree(node.left);
    }
    System.out.print(node.data);
    if (node.right != null) {
       System.out.print(" ");
       printTree(node.right);
    }
}

Answer 7

It's sometimes hard to recognize a return that's not at the end. Most people are accustomed to finding it here. Also, a return that returns nothing can be confusing too. A more obvious way to write it would be:

private void printTree(Node node) {
    if(node!=null) {
        printTree(node.left);
        System.out.print(node.data+" ");
        printTree(node.right);
    }
}

So, simply, "if there is a node, visit it"!