xiromdim
asked on
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;
}
>> 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.
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.
> 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().
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().
>> 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.
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.
^^^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.
BTW: The code also leaks memory because the nodes allocated are never free'd.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
when you say there are memory leaks, where are they, and with what code can I avoid it?
>> 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.
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.
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.