CODEWITHSUNDEEP
javarecursion
Little
Little

Reputation: 3477

How to trace this recursive function?

I have found this Java recursive program for adding an element into a binary search tree:

public void add(int e){
    root=add(root, e);
}
public Node add(Node n, int e){
    if (n==null){
        n=new Node(e);
    } else {
        if (e<n.elem){
            n.left=add(n.left,e);
        } else{
            n.right=add(n.right,e);
        }
    }
    return n;
}

What I do not understand is why it has to return n at the end and then assign it to root again.

Upvotes: 3

Views: 152

Answers (2)

MaxG
MaxG

Reputation: 1077

If you want to understand the recursion, you need to look at the conditions that end It: if (n==null) n=new Node(e);.

This means that the last call will be when Node n is null. When will that be? In one of the leafs. Only then will there be created another object which is added to the tree.

After that, it's only the logic of the return n: After the last call, n is: new Node(e). Who will the new Node be assigned to? Some (former) leaf's n.left or n.right. The same logic precipitates up the tree until the first call to the method add is reached in the stack. That will return the full updated tree - the final product you wanted.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

The reason for the assignment is that Java has only one method of passing parameters - by value.

A reference to root is passed to add method by value. However, add needs to modify a node passed to it as a root: for example, when you add the first node to the tree, the value of root is null, but it needs to become non-null after adding a node.

An idiom to work around this limitation is to make a method that returns the modified value, and assign it back to the parameter. That is what your add method is doing here

root=add(root,e);

and here

n.left = add(n.left, e);
n.right = add(n.right, e);

Upvotes: 4

Related Questions