Binary Tree Insertion Not Working

Question

I have the following code for inserting nodes into a tree. The problem is that the code is not working, there is no compilation error, but the output isn't proper. The code is as follows:

#include <stdio.h>

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

node * insertNode(node *root, int value) {
    if(root == NULL) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data = value;
        new_node->left = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if(root->data < value) {
            printf("%s\n", "Right subtree");
            insertNode(root->right, value);
        } else {
            printf("%s\n", "Left subtree");
            insertNode(root->left, value);
        }
    }
    return root;
}

void printTree(node *root) {
    if(root != NULL) {
    if(root->left != NULL) {
        printTree(root->left);
    }
    printf("%d ", root->data);
    if(root->right != NULL) {
        printTree(root->right);
    }
    }
    else {
        printf("%s\n", "root is null");
        return;
    }
}

int main()
{
    node *root = new node;
    root->data = 1;
    root->left = NULL;
    root->right = NULL;
    root = insertNode(root, 2);
    printTree(root);
    return 0;
}

Where am I going wrong?

Answer 1

You forgot to assigne the return value of recursive function insertNode. Change insertNode(root->right, value) to root->right = insertNode(root->right, value); and insertNode(root->left, value) to root->left = insertNode(root->left, value);. The first paramter of your function insertNode is an input paramter only, the output is your return value. Adapt your code like this:

node * insertNode(node *root, int value) {
    if( root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( root->data < value ) {
            printf("%s\n", "Right subtree");
            root->right = insertNode( root->right, value );
          //            ^ assigne possibly new right node
        } else {
            printf("%s\n", "Left subtree");
            root->left = insertNode( root->left, value );
          //           ^ assigne possibly new left node
        }
    }
    return root;
}

An other solution wold be to change signature of function insertNodeand pass the parameter by pointer:

void insertNode(node **root, int value) {
                 //  ^^ in and output parameter
    if( *root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        *root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( (*root)->data < value ) {
            printf("%s\n", "Right subtree");
            insertNode( &((*root)->right), value );
        } else {
            printf("%s\n", "Left subtree");
            insertNode( &((*root)->left), value );
        }
    }
}

int main()
{
    node *root  = new node;
    root->data  = 1;
    root->left  = NULL;
    root->right = NULL;
    insertNode( &root, 2 );
             // ^
    printTree(root);
    return 0;
}

Note you never delete your allocated nodes.