CODEWITHSUNDEEP
javarecursionwhile-loopbinary-search-tree
COLD ICE
COLD ICE

Reputation: 850

Changing the recursive insertion of the (binary Search tree) to non-recursive?

I am trying to change my recursive insert method of the BST into non-recursive( maybe While loop) The reason for this changing because I want to see if it is possible.

Here is the code of insertion:

public void insert(String value)
{
    //The node is stored in the root
    root = insert(value,root);
}


private Character insert(String value,Character current)
{   
    if(current == null)
    {
        //Add the root if the tree empty 
     current = new Character(value);
    }
    else
        //If the value that we want to insert < root value, then keep going to left till 
        //it's empty then inserted at left end. Done by recursion 
        if(value.compareTo(current.getElement())<=-1)
        {
            current.setLeft(insert(value,current.getLeft()));
        }
        else
            //If the value that we want to insert > root value, then keep going to right till 
            //it's empty then inserted at right end. Done by recursion 
            if(value.compareTo(current.getElement())>=1)
            {
                current.setRight(insert(value,current.getRight()));
            }
            else
            {
                //Else, the number we want to insert in already in the tree
                System.out.println("Duplicate numbers inserted" + current.getElement());
            }
    //returning the node tree so that we store it in the root 
    return current;
}

Could I change this code into non recursive ?

Cheers

Upvotes: 0

Views: 3871

Answers (3)

prashant jagwani
prashant jagwani

Reputation: 1

Insert using while loop

public Node insert(Node root,int n) {
  while (true) {
    if (root.data>n) {
      if (root.left==null) {
          root.left= new Node(n);
          return (root.left);
      }

      root=root.left;
    }
    else if (root.data<n) {
      if (root.right == null) {
          root.right= new Node(n);
      }
    }
  }
}

Upvotes: 0

KH.Lee
KH.Lee

Reputation: 142

Yes, but you need to alter the data structure a little bit to make it works. The node has to know its left child and right child.

The algorithm looks like this:

current = root;
while(current != null){
   if(value.compareTo(current.getElement())<=-1)
   {
        current = current.left_child;
   }else if(value.compareTo(current.getElement())>=1){
        current = current.right_child;
   }else{
        // Duplication
   }
}

Actually there are some good examples before, you may want to check those out first:

Upvotes: 1

Eric
Eric

Reputation: 2705

Yes, you could define your insert function non-recursively.

However, to do this, your insert function will have to define in-order traversal iterator for BST, which is recursively defined.

I believe there is a way to define in-order traversal non-recursively, but depending on implementation this can be very inefficient.

BST itself is basically recursively defined, and it is always efficient to define your insert function recursively. (I could write some pseudo-code if you really need it, but I think it is kind of meaningless and I do not know about the implementation detail of your in-order traversal iterator)

Please don't forget to select this as an answer :-)

Upvotes: 1

Related Questions