How to trace this recursive function?

Question

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.

The return n statement at the end is called after the recursive calls to the left and right have finished. You should review a tutorial (or textbook) covering recursion. — Tim Biegeleisen
– Tim Biegeleisen, Commented Jun 17, 2016 at 1:25
The best way to understand this is to do it with pencil and paper and start with an empty tree. Then trace through the code and add the values 2, 4, 1, and 5. You'll notice that root refers to the actual tree root only on the first call. After that, as you get more than one level down, root refers to the root of the current subtree. — Jim Garrison
– Jim Garrison, Commented Jun 17, 2016 at 1:26

Sergey Kalinichenko · Accepted Answer · 2016-06-17 01:26:46Z

4

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);

answered Jun 17, 2016 at 1:26

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

HopefullyHelpful Over a year ago

Is this version of the algorithm considered better or would checking for null and acting accordingly before going down the next layer of recursion be equally as valid and good?

Sergey Kalinichenko Over a year ago

@HopefullyHelpful You could do without assignment, but then you'd need to null-check in three places - the top level void add, and both branches of the conditional. This implementation, on the other hand, has a single null check, so it is shorter.

MaxG · Accepted Answer · 2016-06-17 01:52:40Z

0

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.

edited Jun 17, 2016 at 1:52

answered Jun 17, 2016 at 1:33

MaxG

1,0772 gold badges13 silver badges27 bronze badges

Collectives™ on Stack Overflow

How to trace this recursive function?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related