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;
}

Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you probably want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — Andreas Wenzel, Oct 09 '20 at 01:44
Discuss the effects of `root=root->left;` with [your rubber duck.](https://en.wikipedia.org/wiki/Rubber_duck_debugging) — user4581301, Oct 09 '20 at 02:02
From looking at your code, it seems that 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 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`. — Andreas Wenzel, Oct 09 '20 at 02:04
Instead of making `root` a global variable, you may want to make it a local variable of `main` and pass it as a function parameter to `insert`. This will also make the recursive function call easier. — Andreas Wenzel, Oct 09 '20 at 02:19
Recommendation: Get rid of the global `root`. It's making things harder for you in several ways (for example, you can't have two BSTs at the same time) and can become a debugging nightmare. Pass the node in by reference with something like `void insert(BTNode* & location, int i)` — user4581301, Oct 09 '20 at 02:19
Note, there are specific differences between a *Binary Tree* and a [Binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree). — David C. Rankin, Oct 09 '20 at 03:04

Hikmat Farhat · Answer 1 · 2020-10-14T07:03:36.453

The effect of your code is the following

insert(5): creates a new BTNode with value 5 and assign it to root
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
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);
}

score 0 · Answer 2 · answered Oct 09 '20 at 03:00

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;
}

score 0 · Answer 3 · answered Oct 09 '20 at 21:01

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 );

    [...]
}

Binary Search Tree--Inserting a Node

3 Answers3