Method recursion (Java)

Question

I ran into a perplex situation while I was trying to understand the binary search tree. I am baffled by the way the method recursion is happening here when a method is called, say inOrder(). Below is the code:

public class Node {
  int data;
  Node left;
  Node right;

public Node (int data) {
    this.data = data;
    left = null;
    right = null;
}
public Node() {
    left = null;
    right = null;
}
public int getData() {
    return data;
 }
}
====================
public class BinarySearch {
  Node root;

public BinarySearch() {
    root = null;
}
public void insert(int data) {
    Node newNode = new Node();
    newNode.data = data;
    if(root == null) {
        root = newNode;
        System.out.println("root =" + root.getData());
    } else {
        Node current = root;
        Node parent;
        while(true) {
            parent = current;
            if(data < current.data) {
                current = current.left;
                if(current == null){
                    parent.left = newNode;
                    break;
                }
        } else {
                current = current.right;
                if(current == null) {
                    parent.right = newNode;
                    break;
                }
            }
        }
    }
}
public void inOrder() {
    inOrder(root);
}
private void inOrder(Node n) {
    if(n != null) {
        inOrder(n.left);
        System.out.print(n.getData() + " ");
        inOrder(n.right);
    }
  }
}
===================
 public class BTree {
    public static void main(String[] args) {
      BinarySearch bst = new BinarySearch();
      bst.insert(10);
      bst.insert(4);
      bst.insert(11);
      bst.inOrder();
   }
}
o/p:
root = 10
4 10 11

Pardon me for the lengthy code, but I hoped you will need it complete.

When the inOrder() method is called, the compiler moves to the extreme left until Node n becomes null and exits the method based on the if statement, however, the immediate step the compiler is looking for after the if for false is System.out.print(n.getData() + " "); which is again inside the 'if' statement - This functionality amuses me a lot. I mean,

1) How is the compiler going to the line System.out.print when the if boolean is still false(because Node n is null) ?

2) Even if it goes to the print, how does n.getData() has a value(o/p: 4) when Node n actually reduced to null?

Thanks ahead!

Answer 1

I agree with the Wang's answer. The java program pauses the execution of 4 (as you are recursively calling the method inOrder(4->left) i.e. inOrder(null).Now, it does not enter the condition as it fails).Now, the execution of 4 resumes and prints out the value 4 and then continues. I hope this helps.

Answer 2

So, when inOrder() hits the node "4" it invokes another inOrder() on the left node of the node "4", this time it's a null value, so it exits, and continues executing the inOrder() on node 4, prints the value of node 4, then invokes inOrder() again on the right side of the node which is -again- null, reaches the end of the function and returns back to the previous node. also as Elliott Frisch said: try a debugger to understand the method's stack.

Answer 3

The program doesn't go to the line System.out.print if it's going into an empty left node. The BST that your program has assembled has 10 as the root, 4 as the left branch of the root, and 11 as the right branch of the root. When inOrder() is called, after going to the left branch onto node.data=4, the program then attempts to look at the left branch of the node.data=4. That left branch is null, so the value of 4 is printed.

You can verify this by placing

System.out.print(n.getData() + " ");

above

if(n != null) {

And you'll encounter an exception.