Insert function for every binary tree

Question

If i have for example 2 binary trees:

typedef struct node {
    int key;
    struct node *left, *right;
} node;

node* root1
node* root2

I've tried this function to insert nodes:

void insert(node* root, int key) {
    node *p, *q;
    p = (node*) calloc(1,sizeof(node);
    p->key = key;
    if (root == NULL) {
        root = p;
        return;
    }
    q = root;
    for (;;) {
        if (key < q->key) {
            if (q->left == 0) {
                q->left = p;
                return;
            } else q = q->left;
        } else if (key > q->key) {
            if (q->right == 0) {
                q->right = p;
                return;
            } else q = q->right;
        } else {
            free(p);
            return;
        }
    }
}

but after call insert(root1,10) the tree root1 remains untouched. I suppose it happens because root variable inside function is changed locally.

How i should implement the function that will receive as argument the tree in which i want to insert nodes?

Right, to have a change the pointer itself reflected on the outside you'll need to pass it in as a double-pointer (**). — 500 - Internal Server Error
– 500 - Internal Server Error, Commented May 3, 2021 at 16:17
Compile your C code with GCC invoked as gcc -Wall -Wextra -g then use valgrind and the GDB debugger to understand the behavior of your program. Read Modern C and the documentation of your compiler and debugger. Be aware that StackOverflow is not a do-my-homework website — Basile Starynkevitch
– Basile Starynkevitch, Commented May 3, 2021 at 16:21
Read also about read-black trees and study for inspiration the source code of Glib — Basile Starynkevitch
– Basile Starynkevitch, Commented May 3, 2021 at 16:24

rohit_r · Accepted Answer · 2021-05-03 16:57:37Z

2

You could always return a pointer to the root, like this

node* insert(node* root, int key) {
    node *p, *q;
    p = (node*) calloc(1,sizeof(node));
    p->key = key;
    if (root == NULL) {
        root = p;
        return root;
    }
    q = root;
    for (;;) {
        if (key < q->key) {
            if (q->left == 0) {
                q->left = p;
                return root;
            } else q = q->left;
        } else if (key > q->key) {
            if (q->right == 0) {
                q->right = p;
                return root;
            } else q = q->right;
        } else {
            free(p);
            return root;
        }
    }
}

And you create your tree like -

node* root1 = NULL;
root1 = insert(root1,3)

edited May 3, 2021 at 16:57

answered May 3, 2021 at 16:37

rohit_r

7132 gold badges7 silver badges20 bronze badges

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

Collectives™ on Stack Overflow

Insert function for every binary tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related