CODEWITHSUNDEEP
cinsertiterationbinary-treebinary-search-tree
Ilias Mentz
Ilias Mentz

Reputation: 520

Binary Search Tree Insertion C without recursion

I am new to the page and I am really stuck at my university's homework to recreate a function that inserts nodes to the tree without Recursion. I have been given the Recursive method and I need to convert it to Iterative. This is the given Recursive Code:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
   if (!root)
   {
      root = newnode;
      root->left = root->right=NULL;
   }
   else if (newnode->entry < root->entry)
   {  
      root->left = InsertTree(root->left, newnode);
   }
   else
   {
      root->right = InsertTree(root->right, newnode);
   }
   return root;
}

and I made this one:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode)
{
   if (!root)
   {
      root = newnode;
      root->left = root->right=NULL;
   }  
   else 
   {
      TreeNode * temp = root, *prev = NULL;

      while(temp)
      {
        if (temp->entry < newnode->entry)
          temp = temp->right;
        else
          temp = temp->left;
      }
      newnode;
      temp->left = temp->right = NULL;
   }
   return root;
}

it works for the first elements but it doesn't save the rest elements. Any ideas? Thanks in advance

Upvotes: 3

Views: 14223

Answers (2)

user6214276
user6214276

Reputation:

This is the code to insert an element iteratively. Since the new element to insert has already been created/allocated there is no point in not initialise the left/right field of the struct as soon as the element is created.

   TreeNode *InsertTree(TreeNode *root, TreeNode *newnode){

         //assuming newnode->left/right already == NULL
         if(root==NULL){
           root = newnode;
         }
         else {
           TreeNode * prev = NULL;
           TreeNode * curr = root;
           while(curr != NULL){
              prev = curr;
              if(curr -> entry < newnode -> entry) curr = curr -> right;
              else curr = curr -> left;
           }
           if (prev -> entry < newnode -> entry) prev -> right = newnode;
           else prev -> left = newnode;

         }
         return root;
     }

Upvotes: 4

Joop Eggen
Joop Eggen

Reputation: 109557

The (un)usage of prev indicates the awareness that the recursive results need to be patched. As already a solution is given by others, here the "ideal" solution, using pointer aliases.

   TreeNode **current = &root;
   while (*current)
   {
       if (newnode->entry < (*current)->entry)
       {
           current = &(*current)->left;
       }
       else
       {
           current = &(*current)->right;
       }
   }
   *current = newnode;
   newnode->left = newnode->right = NULL;
   return root;

current will at the end point to root, or a left/right of a node; being null.

Note that this usage of aliases does not exist in some other languages like java. One of the very few advantages of C.

The & prefix-operator takes the address of the variable.

Upvotes: 5

Related Questions