Insert a node in BST with global root

Question

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

node* root;   //global root

node* getNode(int item)
{
    node* new_node = new node;
    new_node->data = item;
    new_node->left=new_node->right=NULL;
    return new_node;
}

node* insert(node* localroot, int item)
{

    if(localroot == NULL){
        localroot = getNode(item);
    }
    else if(item < localroot->data)
        localroot->left = insert(localroot->left, item);
    else if(item > localroot->data)
        localroot->right = insert(localroot->right, item);
    root = localroot;
    return root;   //Why do I have to return root if it is global? 
                   //without this output is wrong
}

void inorder(node* root)
{
    if(root != NULL){
        inorder(root->left);
        std::cout << root->data << ' ';
        inorder(root->right);
    }
}

void postorder(node* root)
{
    if(root != NULL){
        postorder(root->left);
        postorder(root->right);
        std::cout << root->data << ' ';
    }
}

int main()
{
    insert(root, 15);
    insert(root, 9);
    insert(root, 2);
    insert(root, 1);
    insert(root, 4);
    insert(root, 18);

    std::cout<<"inorder traversal of tree is: ";
    inorder(root);
    std::cout << "\nPostOrder: ";
    postorder(root);

    return 0;
}

Usually in main we call insert like root = insert(root, 10);(where root is declared inside main()).
I wanted to declare root globaly but the insert function cannot be void it has to return node* value can I get an explanation for this.
And if there is a better way please do share(actually I want to make insert to be void type).
Regards,

Answer 1

The way you wrote insert requires that it always returns the node it modified or created. This ensures that insert on a node that has no children sets the correct member (left or right).

You can rewrite root to be purely imperative by passing in a reference to a pointer to be set:

void insert(int item, node*& localroot = root) {
    if (localroot == nullptr) {
        localroot = getNode(item);
        return;
    }

    if (item == localroot->data) {
        return;
    } else if(item < localroot->data) {
        insert(item, localroot->left);
    } else if(item > localroot->data) {
        insert(item, localroot->right);
    }
}

The key point to realize is that assignments to localroot will be reflected in the data structure, so:

• when you call insert(item) for the first time, localroot is a reference to root which is a null pointer. Thus, the first clause applies and you overwrite localRoot with a new node. Because localRoot is a reference to root, that gets updated as well.
• On subsequent calls to insert, you will descend down the tree until you end up at a node N where you have to go down further, but the child is nullptr. When you descend now, localRoot is bound to N->left or N->right, and again the first clause will overwrite that value with a pointer to the freshly created node.

If the default parameter is too magical for you, split into two functions:

void insert_helper(int item, node*& localroot) {
    // as above
}

void insert(int item) {
    insert_helper(item, root);
}

Answer 2

The return type of your function insert means that you have to call it the following way

root = insert(root, 15);

Within your function these statements

root = localroot;
return root;   //Why do I have to return root if it is global? 
               //without this output is wrong

are wrong.

Using your function declaration the function can be defined the following way

node* insert( node* localroot, int item )
{

    if ( localroot == NULL ){
        localroot = getNode( item );
    }
    else if ( item < localroot->data )
        localroot->left = insert( localroot->left, item );
    else if ( item > localroot->data )
        localroot->right = insert( localroot->right, item );

    return localroot; 
}