Understanding stack unwinding in recursion (tree traversal)

Question

I am writing a program to traverse a binary search tree.Here's my code:

Main.java

public class Main {

public static void main(String[] args) {
 BinaryTree binaryTree = new BinaryTree();
binaryTree.add(50);
binaryTree.add(40);
binaryTree.add(39);
binaryTree.add(42);
binaryTree.add(41);
binaryTree.add(43);
binaryTree.add(55);
binaryTree.add(65);
binaryTree.add(60);
binaryTree.inOrderTraversal(binaryTree.root);
} 
}

Node.java

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


public Node(int d)
{
data = d;
left = null;
right = null;
}
}

BinaryTree.java

public class BinaryTree {
Node root = null;
public void add(int d)
{
Node newNode =  new Node(d);
if(root!=null)
{


    Node futureParent = root;
    while(true)
    {
    if(newNode.data < futureParent.data)      //going left
    {
        if(futureParent.left == null)
        {
            futureParent.left = newNode;
            newNode.parent = futureParent;
            break;
        }
        futureParent = futureParent.left;

    }
    else
    {
        if(futureParent.right == null)
        {
            futureParent.right = newNode;
            newNode.parent = futureParent;
            break;
        }
        futureParent = futureParent.right;
    }

    }

}
else
{
    root = newNode;
}
}
public void inOrderTraversal(Node node)
{
if(node!=null)
{
inOrderTraversal(node.left);
System.out.println(node.data);
inOrderTraversal(node.right);
}
}
}

I understand the addition process perfectly but I have trouble understanding the traversal. Now, the tree I am working with, for better reference is this:

The first statement in the inOrderTraversal() function visits 50,40 then 39 and finally hits null making the if condition false after which 39 is printed and is searched for a right child.After this the first statement stops executing and the stack unwinds for the 2nd and 3rd statements(inOrderTraversal(node.right) and print(node.data)) which leads to printing 40 and traversing to 41 which is the part I dont understand, i.e. how does the compiler restart statement 1 (inOrderTraversal(node.left)) after it has stopped executing as soon as there is fresh stuff in the stack.

Answer 1

Your code doesn't work as it is, it will iterate forever over the node 39. The method inOrderTraversal() will indeed go to the left node, but will cycle over it forever because of the while. Each stack frame has it's own copy of the variables. When entering the method, variable node gets a copy of the object reference passed as argument.

One way to think about recursion is that is similar to using a while loop, but instead of while, you have an if. Here's how the method should look like:

    public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.println(node.data);
        inOrderTraversal(node.right);
    }
}

When you traverse the tree, you want to print first the smaller value, which is stored in left most node, so you use inOrderTraversal(node.left); to get to if. When you arrive at a null node, this means it's parent is the left-most node, so you print it. After that you go to the right node and repeat the process. It's like splitting the tree in smaller sub trees until you can't divide them any more and print their value.

Each time you call a method (recursive or not), a new stack frame is allocated (push onto the stack) and after the method finishes, the stack is removed (pop), freeing the space for garbage collection. These stacks frames are only a temporary space where local variables live. The object member variables live in another place called the heap which has a longer life duration than the stack.

The JVM handles the allocation of these spaces and the garbage collector frees them depending on the life of objects/variables. Depending on how much they live, there are a few generations (that's what they are called). All start on the eden (young) generation and if the garbage collector doesn't reclaim the space since they are still alive, they are moved to the survivor generation, after which if they still aren't collected, they move to the last one, the tenured generation. The longer the objects live, the rarer they are checked by the GC. This means that while the objects in the eden are collected pretty fast, the rest of the generations are checked not so often. There is also another space called the permanent generation (permgen) where constants used to live (like string literals) and where classes are stored.