Insert into binary search tree. Nodes replacing

Question

I use this bit of code to create a new node and insert it into a binary search tree. It inserts the root properly, the same with its first right and left children but anything after that seems to replace the already existing child.

For example:

     7
  2     15

If I insert 10 now it will replace 15 instead of becomming its left child.

Node * createNode(Element elem)
{
    Node * newNode = new Node;
    newNode->elem = elem;
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->parent = nullptr;
    return newNode;
}

bool insertElem(BST & tree, Element elem)
{
    Node * newNode = createNode(elem);
    if (!tree.root)
    {
        tree.root = newNode;
        return true;
    }
    else
    {
        return insertElem(newNode, tree.root);
    }
}

bool insertElem(Node * node, Node * root)
{
    if (node->elem.key == root->elem.key) return false; // already exists
    if (node->elem.key > root->elem.key) // goes to the right
    {
        if (root->right) insertElem(node, root->right);
        node->parent = root;
        root->right = node;
        return true;
    }
    if (node->elem.key < root->elem.key) // goes to the left
    {
        if (root->left) insertElem(node, root->left);
        node->parent = root;
        root->left = node;
        return true;
    }
    return false;
}

Which debugger have you used to trace the steps when inserting a new node? — lit

WhozCraig WhozCraig · Accepted Answer · 2017-05-15T03:36:44

Your logic for left and right decension should not be blindly overwriting root->left and/or root->right. Nor should you allocate a new node until you know you're going to insert into the tree. Finally, reference to point (or pointer to pointer, but this is C++, after all) makes the algorithm considerably easier to understand:

The general recursive insertion looks like this:

#include <iostream>
#include <random>

struct Node
{
    int value;
    Node *left;
    Node *right;

    Node(int arg) : value(arg), left(), right()
    {
    }
};

void insertElem(Node *& root, int value)
{
    if (root)
    {
        if (value < root->value )
            insertElem(root->left, value);
        else if (root->value < value)
            insertElem(root->right, value);
        // else equivalent, do nothing
    }
    else
    {
        root = new Node(value);
    }
}

void inorder(const Node* root)
{
    if (!root)
        return;

    inorder(root->left);
    std::cout << root->value << ' ';
    inorder(root->right);
}

void delete_tree(Node *& root)
{
    if (root)
    {
        delete_tree(root->right);
        delete_tree(root->left);
        delete root;
        root = nullptr;
    }
}

int main()
{
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<> dist(1,10);

    Node *root = nullptr;
    for (size_t i=0; i<10; ++i)
    {
        int value = dist(rng);
        std::cout << value << ' ';
        insertElem(root, value);
    }
    std::cout.put('\n');

    inorder(root);
    std::cout.put('\n');

    delete_tree(root);
}

Output (example)

5 7 6 1 3 5 7 3 1 1 
1 3 5 6 7

Notice this is an example that both demonstrates the tree built correctly (thus proper sort order), but also elimination of duplicates.

What makes this work is the pointers descending as references to the actual node pointers of the tree, including the initial root pointer which starts as nullptr in main().

To allow duplicates, all that must be done is a few small changes to the insertion routine:

void insertElem(Node *& root, int value)
{
    if (root)
    {
        if (value < root->value )
            insertElem(root->left, value);
        else // no right test, just descend
            insertElem(root->right, value);
    }
    else
    {
        root = new Node(value);
    }
}

Changing only that a sample output looks like this:

2 9 4 2 2 4 7 2 5 6 
2 2 2 2 4 4 5 6 7 9

Adapt as-needed.

Insert into binary search tree. Nodes replacing

1 Answers