Program not showing the values inserted in a binary search tree-CodePudding

I have tried writing a code to implement a binary search tree, however when I run my code outputs nothing and closes a program. I think my insert function is correct since I wrote cout<<"yes" at multiple places in the insert function, and to show all the nodes of the binary search tree I have used in order traversal which is done recursively inside a simple function. Here is my code:

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *right;
    Node *left;
};

void insert(Node **root_ref, int value)
{
    Node *temp = new Node();
    temp->data = value;
    temp->right = NULL;
    temp->left = NULL;
    Node *current = *root_ref;
    if (*root_ref == NULL)
    {
        *root_ref = temp;
        return;
    }
    while (current != NULL)
    {
        if ((temp->data < current->data) && (current->left == NULL))
        {
            current->left = temp;
            return;
        }
        else if ((temp->data > current->data) && (current->right == NULL))
        {
            current->right = temp;
            return;
        }
        else if ((temp->data > current->data))
        {
            current = current->right;
        }
        else
        {
            current = current->left;
        }
    }
}

void printinorder(Node *root1)
{
    printinorder(root1->left);
    cout << " " << root1->data << " ";
    printinorder(root1->right);
}

int main()
{
    Node *root = NULL;
    insert(&root, 60);
    insert(&root, 50);
    insert(&root, 70);
    insert(&root, 30);
    insert(&root, 53);
    insert(&root, 80);
    insert(&root, 65);
    printinorder(root);
}

CodePudding user response：

For starters the function insert can produce a memory leak when a value is added to the tree when there is already a node with the same value because in this case only this else statement can be evaluated

while (current != NULL)
{
    //...
    else
    {
        current = current->left;
    }
}

So the loop will end its iterations and nothing will be added to the tree though a node was already allocated.

The function can be written for example the following way

void insert( Node **root_ref, int value )
{
    Node *temp = new Node { value, nullptr, nullptr };

    while ( *root_ref != nullptr )
    {
        if ( ( *root_ref )->data < value )
        {
            root_ref = &( *root_ref )->right;
        }
        else
        {
            root_ref = &( *root_ref )->left;
        }
    }

    *root_ref = temp;
}

In the recursive function printinorder

void printinorder(Node *root1)
{
    printinorder(root1->left);
    cout << " " << root1->data << " ";
    printinorder(root1->right);
}

you are not checking whether the passed argument is equal to nullptr. So the function invokes undefined behavior.

The function can be written the following way

std::ostream & printinorder( const Node *root, std::ostream &os = std::cout )
{
    if ( root != nullptr )
    {
        printinorder( root->left, os );
        os << " " << root->data << " ";
        printinorder( root->right, os );
    }

    return os;
}