Binary Search Tree--Inserting a Node

Question

I am trying to implement a function to insert a node into a binary search tree. I am using the following code, but when I try to print to screen all I see is "root =1". Any suggestions on what I am doing wrong?

#include <iostream>

class BTNode {
public:
   int item;
   BTNode *left;
   BTNode *right;
   BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;
void insert(int i) {
   if (root==nullptr)
      root=new BTNode(i);
   else if(i<root->item){
      root=root->left;
      insert(i);
   }
   else{
      root=root->right;
      insert(i);
   }
}

int main()
{
   insert (5);
   insert (10);
   insert (1);
   
   if (root) 
   {
      std::cout << "root = " << root->item << std::endl;
      if (root->left)
         std::cout << "root->left = " << root->left->item << std::endl;
      if (root->right)
         std::cout << "root->right = " << root->right->item << std::endl;
   }
   
   return 0;
}

Answer 1

The effect of your code is the following

1. insert(5): creates a new BTNode with value 5 and assign it to root
2. insert(10): create a new BTNode with value 10 and assign it to root. You no longer have a reference to the previously created node
3. insert(1): create a new BTNode with value 1 and assign it to root. You no longer have a reference to either of the two previously created nodes.

You can implement the insert function this way, which usually are member function of the BTNode class this is why i am calling them private/public but since you choose to implement them as function outside the class i am keep them that way.

First you have a public insert function

void insert(int i){
      insert( i,root);// call the private function. see below
}

second you have a private insert function (Note that the pointer variable should be passed by reference otherwise it will change a copy of the pointer)

void insert(int i,BTNode *& t){
    if(t==nullptr)t=new Node(i);
    else if(i<t->item)insert(i,t->left);
    else insert(i,t->right);
}

Answer 2

Your insert function is properly adding the new node to the tree. However, as a side effect, it is sometimes changing the global variable root to point to the left or right node of the root, so that the rest of the tree gets lost. Your insert function should never change the root, unless root == nullptr.

Therefore, I suggest you rewrite your function insert so that it does not use root at all, but instead receives a pointer to the node as a function parameter. This pointer must be passed by reference and not be value, because the function insert must be able to change the actual pointer that is passed, if it is nullptr. In order to accomplish this, you could for example change the function prototype to the following:

void insert( BTNode &*pp_node, int i );

This will also make your recursive function call work properly, as the function can now be rewritten like this:

void insert( BTNode *&node, int i )
{
    if ( node == nullptr )
        node = new BTNode( i );
    else if ( i < node->item )
        insert( node->left, i );
    else
        insert( node->right, i );
}

Your function main would have to be rewritten like this:

int main()
{
    insert( root, 5 );
    insert( root, 10 );
    insert( root, 1 );

    [...]
}

However, since you no longer need root to be a global variable (because it is passed as a function parameter now), it would probably be better to declare it as a local variable, like this:

int main()
{
    BTNode *root = nullptr;

    insert( root, 5 );
    insert( root, 10 );
    insert( root, 1 );

    [...]
}

Although this recursive solution to the problem works, an iterative solution would be more efficient. Therefore, you may want to rewrite your function insert like this:

void insert( BTNode **pp_node, int i )
{
    while ( *pp_node != nullptr )
    {
        if ( i < (*pp_node)->item )
            pp_node = &(*pp_node)->left;
        else
            pp_node = &(*pp_node)->right;
    }

    *pp_node = new BTNode( i );
}

This solution requires a pointer to a pointer (a so-called double pointer) instead of a reference to a pointer, because references can't be reassigned.

However, since the function prototype of insert has now changed, you would also have to adapt the function main accordingly:

int main()
{
    BTNode *root = nullptr;

    insert( &root, 5 );
    insert( &root, 10 );
    insert( &root, 1 );

    [...]
}

Answer 3

I'v wrote down code below.

BTNode *root = nullptr;
BTNode* insert_node(int ivalue, BTNode* _parent) {
    if (_parent == nullptr) {
        return _parent = new BTNode(ivalue);
    }
    else if (ivalue<_parent->item) {
        _parent->left = insert_node(ivalue, _parent->left);
    }
    else {
        _parent->right = insert_node(ivalue, _parent->right);
    }
    return nullptr;
}
void insert(int i) {
    BTNode*newnode = insert_node(i, root);
    if (newnode)root = newnode;
}

int main()
{
    insert(5);
    insert(10);
    insert(1);
    //insert(2);
    //insert(4);
    if (root)
    {
        std::cout << "root = " << root->item << std::endl;
        if (root->left)
            std::cout << "root->left = " << root->left->item << std::endl;
        if (root->right)
            std::cout << "root->right = " << root->right->item << std::endl;
    }

    return 0;
}