CODEWITHSUNDEEP
javarecursioninsertbinary-treebinary-search-tree
Stacky
Stacky

Reputation: 488

Is binary search tree reconstructed during recursive insertion?

In the regular recursive code for bst, the left and right elements for the tree are set in every recursive call (In t.left= and t.right=). Isn't this constructing the tree again?

Wouldn't it be better to store a reference to previous node and then add the new node to left or right depending upon the value or am I missing something here? Thanks!

      public Elem insert (Elem t, int toInsert)
      {
        if (t == null)
          return new Elem(toInsert,null,null);
        else {
          if (toInsert < t.value)
             t.left  = insert(t.left, toInsert);
          else
             t.right = insert(t.right,toInsert);
          return t;
        }
  }

To insert one new element, the code assigns each and every element or sub trees as left and right. My question is that isn't this an overhead? To insert in a linked list, we simply navigate to the last node and perform linkages there. Here, we perform linkages for the whole tree on each insertion. Is there any alternative to avoid this?

Upvotes: 1

Views: 146

Answers (1)

Chris Gong
Chris Gong

Reputation: 8229

It's not reconstructing the tree, rather, the method traverses through the tree with recursive calls to get to a leaf (a null spot) within the tree so that the new element can be added there. For example, consider this BST,

    6
   / \
  4   8

And let's say you called insert(element 6, 5) (* signifies where we are while traversing through three).

   *6
   / \
  4   8

The method would skip through the first if-statement, and proceed to check the value of 5 in relation to the current element in the method paramter. 5 is less than 6, so the following line is performed, t.left = insert(t.left, toInsert) (think of this as elem6.left = insert(element 4, 5)).

    6
   / \
 *4   8

Now we're on the second method call of insert, this time insert(element 4, 5). The first if-statement is skipped once again and 4 is compared to 5. 5 is greater than 4, so the following line is performed, t.right = insert(t.right,toInsert) (think of this as elem4.right = insert(null, 5)).

    6
   / \
  4   8
   \
    *

Now we're on the third method call of 'insert', this time insert(null, 5) is called so the first if-statement is actually executed and a new object of type Elem is returned. Aka this line is performed, return new Elem(toInsert,null,null) (think of this as return new Elem(5, null, null)).

    6
   / \
  4   8
   \
    *

At this point the call stack begins to decrease after it has grown to three calls. Back to this line, t.right = insert(t.right,toInsert) but instead of insert(t.right, toInsert), it's now new Elem(5, null, null). So element 5 has been assigned to the right side of element 4. Then, the rest of the method is executed, ending with return t. t in this case is the Elem passed through the method, element 4.

    6
   / \
 *4   8
   \
    5

Back to this line (going down the call stack), t.left = insert(t.left, toInsert) but instead of insert(t.left, toInsert), it's now element 4. So the left of element 6 has been assigned to element 4. Then, the rest of the method is executed, ending with return t. t in this case is the Elem passed through the method, element 6. And then the inserting of element 5 has concluded.

   *6
   / \
  4   8
   \
    5

Upvotes: 2

Related Questions