Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 589
  • Last Modified:

BST insertion C code

where is the mistake in the code below?
#include<stdio.h>
#include<stdlib.h>

struct node{
       int val;
       struct node* left;
       struct node* right;
};
typedef struct node* Tree;
void insert(Tree *root,int x){
     
     if (*root==NULL){
                     *root = (struct node*)malloc(sizeof(struct node));
                     (*root)->val=x;
                     (*root)->left=(*root)->right=NULL;
                     return;
                     }
     if (x<(*root)->val) *root=(*root)->left;
     else if (x>(*root)->val)   *root=(*root)->right;
}
void inorder(Tree root){
     
     if (root==NULL) return;
     inorder(root->left);
     printf("%d ",root->val);
     inorder(root->right);
}

int main(){
    Tree root=NULL;
    
    insert(&root,10);
    insert(&root,5);
    insert(&root,1);
    insert(&root,12);
    inorder(root);
    getchar();
    
    return 0;
}

Open in new window

0
xiromdim
Asked:
xiromdim
1 Solution
 
phoffricCommented:
I notice that in your first insertion insert(&root,10), then you go (as you should) into the if (*root==NULL){ path, where you set val=x, and left/right ptrs to NULL (all good).

But on your next insert(&root,5), I do not see where you are setting val=x or setting the left/right ptrs.

Also, if you had a tree, say of depth 5, and if you tried to insert a value, x, which should land, say at depth 5 or 6, then I am not sure I am seeing the traversal down the tree to get to the proper node.
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> Also, if you had a tree, say of depth 5
I don't think this refers to the depth (which will vary depending upon the number of inserts and how balanced the tree is), it's just a value being inserted.

Apart from that I think you have hit the nail on the head. There is no code to insert any value other than the first. The next number that's inserted just overwrites the root node. What should happen is the function should be called recursively, passing either the left or the right node as the root to the next call. This repeats until you are at the leaf, where-upon you add the value. So lines 18 and 19 should look something like this

     if (x<(*root)->val) insert(&(*root)->left, x);
     else if (x>(*root)->val)  insert(&(*root)->right, x);

Note this is completely untested and is just meant as a quick example to put you in the right direction.
0
 
jb1devCommented:
> There is no code to insert any value other than the first.

Right but i think there is an issue with how the root node is being allocated. Otherwise we'd at least see one value when displaying the tree. Currently nothing is there because root is null when it's passed to inorder().

0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
evilrixSenior Software Engineer (Avast)Commented:
>> Otherwise we'd at least see one value when displaying the tree. Currently nothing is there because root is null when it's passed to inorder().
See what I said above, "The next number that's inserted just overwrites the root node." (lines 18 & 19)

*root=(*root)->left;

and

*root=(*root)->right;

both of which are NULL.
0
 
evilrixSenior Software Engineer (Avast)Commented:
^^^put another way, just insert one item and it works, insert more and the tree is corrupted.

BTW: The code also leaks memory because the nodes allocated are never free'd.
0
 
evilrixSenior Software Engineer (Avast)Commented:
This is the code, fixed (apart from the memory leak).
#include<stdio.h>
#include<stdlib.h>

struct node{
   int val;
   struct node* left;
   struct node* right;
};
typedef struct node* Tree;
void insert(Tree *root,int x){

   if (*root==NULL){
      *root = (struct node*)malloc(sizeof(struct node));
      (*root)->val=x;
      (*root)->left=(*root)->right=NULL;
      return;
   }

   if (x<(*root)->val) insert(&(*root)->left, x);
   else if (x>(*root)->val)  insert(&(*root)->right, x);
}

void inorder(Tree root){

   if (root==NULL) return;
   inorder(root->left);
   printf("%d ",root->val);
   inorder(root->right);
}

int main(){
   Tree root=NULL;

   insert(&root,10);
   insert(&root,5);
   insert(&root,1);
   insert(&root,12);
   inorder(root);
   getchar();

   return 0;
}

Open in new window

0
 
xiromdimAuthor Commented:
when you say there are memory leaks, where are they, and with what code can I avoid it?
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> when you say there are memory leaks, where are they, and with what code can I avoid it?
Every time you malloc memory it must be matched with a corresponding free when you are done.

char * p = malloc(sizeof(char));
// use p
free(p);

http://www.cplusplus.com/reference/clibrary/cstdlib/free/

In your code, you need to add a function that traverses the nodes and frees them. Since you have a parent to child relationship you need to work from the bottom up. The simplest way to do this is to have a function similar to 'inorder' that calls itself recursively until it hits a null and then, during the stack unwind phase, it calls free on all the root nodes it was passed.
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now