Recursion while adding nodes in tree data structure

Question

I'm new to understanding and learning data structures.I have tried to implement Tree data structure after searching some tutorials.It seems well but i don't understand the recursive behavior which was a bit strange here.Can someone help me in understanding the code.

I have included some print statements to understand the recursive flow but was not able to understand why the current refernce is not being returned?

public class TreeCheck {
Node root;
private Node addRecursive(Node current, int value) {
if (current == null) {
    return new Node(value);
}

if (value < current.value) {
    current.left = addRecursive(current.left, value);
} else if (value > current.value) {
    current.right = addRecursive(current.right, value);
} else {
    // value already exists
    return current;
}
System.out.println("current is "+current.value); //Please compare in the 
 image why the 
return current;
}


public void add(int value) {
root = addRecursive(root, value);
System.out.println("value is "+root.value);
}

  public static void main(String h[]){
 TreeCheck bt = new TreeCheck();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);


    }

  class Node {
  int value;
  Node left;
  Node right;

   Node(int value) {
    this.value = value;
    right = null;
    left = null;
}
}

Why the current statement is being printed twice and always returns the root element only when the current is re-assigned sometimes?

You are making a recursive call first. This recursive call may make another recursive call. Your logs only print after all recursion is done. To understand it better try adding two logs. First at the beginning of your addRecursive method, like println("START: current is" + ...), and one where the current log is println("END: current is" + ...). Maybe even add some more logs in your if-Statements to clearly see if it's added to the left or the right of the tree. An even better approach would be to take a pen and paper and draw the tree step by step to see how it is created. — ich5003
– ich5003, Commented Aug 17, 2019 at 20:19
@ich5003 Thank you,the query is in the above example when 4 is added ,the current Node(initially was 6) but because of recursion it became 4 and It was not returned,instead of that 6 was returned again.Why is this behavior ?.Why the recursive functions return statement is ignored ? — Rakesh .p
– Rakesh .p, Commented Aug 17, 2019 at 20:26
"current" is not always the value you're trying to add. Take a clear look what happens on the recursive call. You're setting the function parameter current to current.left or current.right. So you're traversing the tree down, node by node, until you find a position where no node exists anymore and then you're adding your value there. Make sure you realize the difference between what "current" and what "value" as your function parameters mean. — ich5003
– ich5003, Commented Aug 17, 2019 at 20:29

davidrhp · Accepted Answer · 2019-08-18 13:32:20Z

4

It isn't printing it right for the following reasons:

First, your add method is always printing "value is " + root.value", which is confusing when trying to figure out how the program adds values.

Second, your add method prints after the value has been inserted, I would restructure it so that it prints the value to be inserted first, and then the path in which the nodes are being checked:

    public void add(int value) {
    // you always printed out the value of the root node with every call to this method
    // I updated it to reflect the input argument
    System.out.println("\nvalue is " + value);
    root = addRecursive(root, value);
}

Now each block is its own insertion and the program flow is easier to trace.

Next: current is actually printing correctly, just in reverse order. Let us say you are inserting 5, the current nodes to be printed will be: the parent of 5, which is 4, then the parent of 4, which is 6.

This image might help to visualize the tree (sorry for my ugly hand writing)

If you want to change the order, do it like this (place the print of current before the if statement):

    private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    System.out.println("current is " + current.value);

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
}

Furthermore, if you would like to see if your insertion into a binary search tree works, you can use this method to print your tree in ascending order:

    public void inOrderPrint(Node node){

    if (node.left != null) {
        inOrderPrint(node.left);
    }

    System.out.println(node.value);

    if (node.right != null) {
        inOrderPrint(node.right);
    }
}

And call it like this in your main:

    public static void main(String h[]) {
    TreeCheck bt = new TreeCheck();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    System.out.println("-------");
    bt.inOrderPrint(bt.root);

}

I hope that was helpful and that I explained it clearly. Please comment if I made an incorrect statement and I will edit the post accordingly.

edited Aug 18, 2019 at 13:32

answered Aug 17, 2019 at 20:44

davidrhp

1251 silver badge5 bronze badges

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

3 Comments

Rakesh .p Over a year ago

Thanks for the answer,My only concern is while traversing through the tree,the root node value 6 checks for it's left node position(which was occupied by 4 already and got to know by recursion)Now after the recursion why the return statement is not returning the reference of 4 Node instead returns the node 6 again to the root. I mean is it like the First call reference will be always returned irrespective of the number of recursions occuring in the method?

davidrhp Over a year ago

Generally speaking, imagine it like this: You have a call stack in which method calls are stored with their respective local variables. If you have 3 recursive calls in a row ` A1(A2(A3))) ` (A is the method, the number is just so I can reference them), it will first add A1 to the call stack, then A2, then A3. None of the methods have returned yet. They will return in reverse order, so the (LIFO, last in first out) so first A3 returns, then A2, then A1. While this is happening, each method has its own version of current. Whichever method call hits a print statement first, will print first.

davidrhp Over a year ago

Try to debug the program step by step. Imagine what each method call does, which arguments are passed into and trace the program that way. Draw the tree and how the nodes are inserted. Draw the method calls with their respective local variables and see when a print statement is reached and with which value of current . Also, the program is executed sequentially, if method A1 calls A2, then A1 will not continue until A2 has returned. Each line is processed sequentially. If A1 calls A2 at line 50, A1 waits there and A2 will start at line 1. Once A2 is done, A1 will proceed on line 51.

Shivansh Narayan · Accepted Answer · 2019-08-17 20:13:54Z

2

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Go through the above article it should help. Happy Learning !!

answered Aug 17, 2019 at 20:13

Shivansh Narayan

5267 silver badges16 bronze badges

2 Comments

Rakesh .p Over a year ago

-Thanks for the answer, but the query is why the recursive return statement is not being returned every time as the current keeps changing.

ich5003 Over a year ago

Drawing the tree by hand while following the algorithm probably answers your question.

Collectives™ on Stack Overflow

Recursion while adding nodes in tree data structure

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related