Jéssica Carneiro Jéssica Carneiro - 1 month ago 5
C Question

Function gets right pointer but returns NULL

I'm creating a binary tree in C in which I use indexes as in a binary search tree. I'm having trouble with a function that finds a node.

My code for the tree is in a separate file and it's the following:

struct node {
struct node *left;
struct node *right;
int index;
void *data;
};

struct node * init_mt()
{
struct node *root = malloc(sizeof(struct node));
root->index = -1;
root->data = NULL;
root->left = root->right = NULL;
return root;
}

void create_mt(struct node *mt, int h, int i)
{
if (h == 0) // end of tree reached
{
mt->index = 0;
mt->left = mt->right = NULL;
return;
}
else
{
mt->index = i;
int l = i-pow(2,h-1);
int r = i+pow(2,h-1);
mt->left = malloc(sizeof(struct node));
mt->right = malloc(sizeof(struct node));
create_mt(mt->left,h-1,l);
create_mt(mt->right,h-1,r);
}
}

struct node * get_node_mt(struct node *mt, int p, int h)
{
if (h == -1) // end of tree reached
{
return NULL;
}
else
{
if (mt->index == p)
{
printf("Found %p\n", mt);
return mt;
}
else if (mt->index > p)
{
get_node_mt(mt->left,p,h-1);
}
else
{
get_node_mt(mt->right,p,h-1);
}
}
}


When I run my main like this (root->left->left is the node index #2):

struct node *root = NULL;
root = init_mt();
create_mt(root,3,8); // root index == 8
printf("%d %p\n", root->left->left->index,root->left->left);
struct node *find;
find = get_node_mt(root,2,3);
printf("%p\n", find);


I get the following output:

2 0x7ffd1dd011a0
Found 0x7ffd1dd011a0
0x0


I don't understand why I get the right pointer both when priting directly using root->left->left and inside the function get_node_mt() but not when I print the pointer I've returned. What am I doing wrong?

Answer

The get_node_mt() function calls itself in two places. Neither of these two places return a value.

struct node * get_node_mt(struct node *mt, int p, int h)
{
    if (h == -1) // end of tree reached
        return NULL;
    else if (mt->index == p)
        return mt;
    else if (mt->index > p)
        get_node_mt(mt->left,p,h-1);
    else
        get_node_mt(mt->right,p,h-1);
}

I reformatted the code a bit and removed a lot of braces. The compiler should've warned about this problem, IMHO.

Comments