binary search tree pointer problem

Question

I tried to implement a binary search tree for the purpose of (re-)learning C. The problem is that the this current = new; does not work as desired because the tree.root is still a null pointer after adding two nodes. What's wrong with that?

#include <stdlib.h>
#include <stdio.h>


typedef struct BinaryNode {
    int key;
    double value;
    struct BinaryNode *left;
    struct BinaryNode *right;
    } BinaryNode;

typedef struct BinaryTree {
    struct BinaryNode *root;
    } BinaryTree;


static void binary_tree_insert_recursive(BinaryNode *current, BinaryNode *new) {
    if (current == NULL || current->key == new->key) {
        current = new;
    } else if (current->key > new->key) {
        binary_tree_insert_recursive(current->left, new);
    } else if (current->key < new->key) {
        binary_tree_insert_recursive(current->right, new);
    }
}

void binary_tree_insert(BinaryTree *tree, int key, double value) {
    BinaryNode *new = (BinaryNode *) malloc(sizeof(BinaryNode));
    new->key = key;
    new->value = value;
    binary_tree_insert_recursive(tree->root, new);
}

int main(void) {
    BinaryTree tree;
    binary_tree_insert(&tree, 5, 123);
    binary_tree_insert(&tree, 10, 123);
    printf("%p\n", tree.root);
    return 0;
}

Thank you!

cnicutar · Accepted Answer · 2011-06-14 19:53:14Z

1

I believe the problem with current = new; is that you are changing your local copy of current. After the function is done, this modification is not visible.

I suspect you want something like:

static void binary_tree_insert_recursive(BinaryNode **current, BinaryNode **new)
{
    if (*current == NULL || (*current)->key == (*new)->key) {
    *current = *new;
    /* ... */

Well explained in the C FAQ.

answered Jun 14, 2011 at 19:53

cnicutar

184k26 gold badges378 silver badges398 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andrei Over a year ago

@ahojnnes: You might need to consider also initializing the "left" and "right" pointers to NULL for every node you create. Also, don't name your variable "new", it's confusing.

xyz-123 Over a year ago

@Andrei: is it not initialized with a null pointer by default?

Andrei Over a year ago

@ahojnnes: They are not requited to be initialized to anything. Some compilers will initialize them to some "easy to see" values such as 0xcccccccc or 0xdeadbeef.

AShelly · Accepted Answer · 2011-06-14 19:54:46Z

1

current is a pointer to a node. When you pass it to binary_tree_insert_recursive from binary_tree_insert the value of the pointer is passed. So although it is changed inside the called function, the change is not reflected in the calling function. You need to modify the function to take the address of the pointer you wish to change:

 static void binary_tree_insert_recursive(BinaryNode **current, BinaryNode *new)
 {
         if (*current == NULL || (*current)->key == new->key)  {
             *current = new;

answered Jun 14, 2011 at 19:54

AShelly

35.9k17 gold badges98 silver badges163 bronze badges

Comments

τεκ · Accepted Answer · 2011-06-14 19:53:54Z

0

all that current = new does is make it so that the variable current points at the thing that new is pointing at. No copying takes place, and the function has no effect on that codepath.

answered Jun 14, 2011 at 19:53

τεκ

3,1441 gold badge18 silver badges14 bronze badges

Comments

stakx - no longer contributing · Accepted Answer · 2012-08-11 13:21:45Z

0

new is a keyword. Choose a different variable name.

edited Aug 11, 2012 at 13:21

stakx - no longer contributing

85.1k20 gold badges176 silver badges277 bronze badges

answered Jun 14, 2011 at 19:50

Paul Sonier

39.6k3 gold badges81 silver badges118 bronze badges

2 Comments

Seva Alekseyev Over a year ago

In C proper it's not. However, who knows what is the OP compiling it like. Didn't even specify the compiler, or the error message.

xyz-123 Over a year ago

I thought this is C++? Nevertheless it does not solve the problem.

Collectives™ on Stack Overflow

binary search tree pointer problem

4 Answers 4

3 Comments

Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related