How to print out Node Values from BinaryTree with continuing number?

I'm trying to travers a Binary Tree and print out the Node Values with a matching number in front of each Node. For better understanding: I'm printing out following lines while Calling my Method:

1. 11 , 2. 33 , 3. 10 , 4. 14 , 5. 27 , 3. 31 , 4. 32

Where as my Goal with the Method ist, to print out the exact same order of the Nodes but with having an increasing Number infront of it, which should indicate the order. Like so:

1. 11
2. 33
3. 10
4. 14
5. 27
6. 31
7. 32

Till know my Method looks like this:

public int mNr(Node k, int Nr) {
        //If the current Node is null, return 0 (currently not making any use of the return)
        if(k == null) {
            return 0;
        } else {
            //If the left Side is not null print out the Left Node with Value 
            if(k.left != null) {
                //increment Nr each time priniting
                System.out.println("Nr: " + ++Nr + " " + k.left.number);
            }
            if(k.right != null) {
                //Same as left Side
                System.out.println("Nr: " + ++Nr + " " + k.right.number);
            }
            //Calling the Method and not incrementing the Nr Parameter because 
            //already incrementing it in the print Statements
            return mNr(k.left, Nr) + mNr(k.right, Nr);
        }
    }

I'm also not quite sure how to use the int -return, even till know I'm not making any use of it. Any Advice for getting the Correct Output would be helpful.

Solution 1:

As each recursive call has its own Nr variable, they don't always have the same value. If in the deeper recursion, Nr is incremented, this does not affect the caller's version of Nr.

As you already seemed to hint to, you can use the return value to communicate back to the caller what the latest value of Nr is, so that the caller can update its own Nr variable, or use it as the caller pleases.

Here is a correction:

public int mNr(Node k, int Nr) {
    if(k == null) {
        return 0;
    } else {
        if(k.left != null) {
            System.out.println("Nr: " + ++Nr + " " + k.left.number);
        }
        if(k.right != null) {
            System.out.println("Nr: " + ++Nr + " " + k.right.number);
        }
        // Use the return value from the left-recursion to feed the right-recursion
        return mNr(k.right, mNr(k.left, Nr));
    }
}

Having said that, this traversal has some other issues:

• The root node is not included in the output
• The traversal has a peculiar order: it is a mix of depth and breadth first. It would make more sense to choose a more popular traversal, like a pre-order traversal (first parent, then left subtree, then right subtree)

So this leads to the following alternative code:

static public int mNr(Node node, int Nr) {
    if (node == null) {
        return Nr;
    }
    System.out.println("Nr: " + ++Nr + " " + node.number);
    return mNr(node.right, mNr(node.left, Nr));
}