Reputation: 1189
i'm trying to implement binary search tree in c. I use lldb to trace my code and i found out when the function PUT return, it return a node pointer with key = 5 and value = 9, and it was assigned to the node pointer P in main.
however when i pass it to the tree_walk function and try to print out everything, it gave me a segmentation fault. can anyone please tell what is wrong with my code. Thank you
typedef struct Node{
int key;
int value;
int size;
struct Node *left;
struct Node *right;
}Node;
Node* put(Node **node, int k, int val){
if(*node == NULL){
Node *newNode = (Node *)malloc(sizeof(Node*));
newNode->key = k;
newNode->value = val;
return newNode;
}else if((*node)-> key == k){
(*node)->value = val;
}else{
int cmp = k > ((*node)->key) ? 1 : 0;
Node **ptr = NULL;
if(cmp == 1){
ptr = &((*node)->right);
(*node)->right = put(ptr, k, val);
}else{
ptr = &((*node)->left);
(*node)->left = put(ptr, k ,val);
}
}
(*node)->size = size((*node)->left) + size((*node)->right) + 1;
return *node;
}
int main(void){
Node *p = NULL;
p = put(&p, 5,9);
tree_walk(p);
}
Upvotes: 0
Views: 82
Reputation: 141633
This line allocates the wrong size:
Node *newNode = (Node *)malloc(sizeof(Node*));
It should be:
Node *newNode = malloc( sizeof *newNode );
You only allocated enough space for a pointer, not for a Node
.
Another problem is that you never initialize newNode->left
and newNode->right
. If the tree_walk
function tries to read them then it causes undefined behaviour.
Upvotes: 3