understanding a part of recursion for a binary search tree

Question

Hello I basically need to implement a recursive function for insertion of a binary tree. I already implemented the chunk of insertion function (wether it's largest or smaller than root) but there's an aspect of confusion.

 public void insert(E data) {
     root = insert(root, data);
}

private Node<E> insert(Node<E> value, E data) {
    if(value == null) {
       return new Node<E>(data);
    }
    else if (data.compareTo(value.data) > 0 )  {
        value.right = insert(value.right, data); 
    }
    else if(data.compareTo(value.data) <= 0) {
        value.left = insert(value.left, data);
    }
    return value; 

}

The problem I have is this line:

  public void insert(E data) {
      root = insert(root, data);
  }

Why do I need that line of code? Is the root actively changing? My partner tried explaining to me how it doesn't change except for the first root.

Is the private function for the recursion always returning the first parent root as the root?

Thank you.

trincot · Accepted Answer · 2025-04-24 18:31:20Z

Why do I need that line of code?

We need that line to determine what the node is where we start the search for the correct insertion point, and the obvious place where such a search should start is at the root of the tree. As this private insert function will be called recursively -- each time with a different node as argument -- it is necessary to also specify the node where to start the search, which is the root node.

That's why we call the private insert function with root as argument.

Is the root actively changing?

No, the root of the tree remains the same one. What changes is the "scope" of the search, i.e. which subtree we will search in. It is essential to realize that the private insert function is called again and again, but each time with a different subtree -- to which the search will be limited. So the parameter which you have called value (NB: node would have been a better name for it) will take different nodes, determined by the caller. Its purpose is to limit the search to a certain subtree, of which that node happens to be the root. The initial call must consider the whole tree, so that initial call will get the root as argument.

Is the private function for the recursion always returning the first parent root as the root?

The function returns the node that is the root of the relevant subtree after the new node has been inserted into that subtree. In most cases that will be the same node that was the root of the subtree at the time the call was made, but obviously it is not the same node when we had passed null as argument to that call. In that case the previously empty subtree (the null) is replaced with a 1-node subtree, i.e. the new node which is the root of its own subtree.

Collectives™ on Stack Overflow

understanding a part of recursion for a binary search tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related