CODEWITHSUNDEEP
c++binary-search-tree
user2411290
user2411290

Reputation: 641

C++ Binary Search Tree implementation does not add every element

I have a simple C++ implementation of a BST. I am only trying to add numbers and to print them out, in order. The problem is that out of the 16 numbers I try to add, I am only able to add 12 (leaving out 32, 15, 14 and 3). The output from my console is shown below:

Printing the tree before adding numbers:
The list is empty
The key 32 has already been added.
The key 15 has already been added.
The key 14 has already been added.
The key 3 has already been added.
Printing the tree in order after adding numbers:
2 4 21 50 52 64 70 76 80 83 87 100
Program ended with exit code: 0

#include <iostream>

using namespace std;
class BST {

private:

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

    node * root;

    void addLeafPrivate(int data, node * n);
    void printInOrderPrivate(node *);


public:

    BST();
    node * createLeaf(int data);
    void addLeaf(int data);
    void printInOrder();


};

int main() {

    int TreeKeys[16]= {50, 76, 21, 4, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 80};
    BST bst;

    cout << "Printing the tree before adding numbers: \n";
    bst.printInOrder();

    for (int i = 0; i < 16; i++) {
        bst.addLeaf(TreeKeys[i]);
    }

    cout << "Printing the tree in order after adding numbers: \n";

    bst.printInOrder();

    return 0;
}

BST::BST() {root = NULL;}

BST::node * BST::createLeaf(int data) {

    node * n = new node;

    n->data = data;
    n->right = NULL;
    n->left = NULL;


    return n;

}

void BST::addLeaf(int data) {
    addLeafPrivate(data, root);
}


void BST::addLeafPrivate(int data, node * n) {

    if (root == NULL) {
        root = createLeaf(data);
    }

    else if (data < n->data) { // add recursively on left left side.
            if (n->left != NULL){
            addLeafPrivate(data, n->left);
            }
            else { // if left is empty
                n->left = createLeaf(data);
            }
        }

        else if (data > root->data) { // add recursively on right left side.
            if (n->right != NULL) {
                addLeafPrivate(data, n->right);
            }
            else { // right is empty
                n->right = createLeaf(data);
            }


        }

    else {
        cout << "The key " << data << " has already been added.\n";
    }
}

void BST::printInOrder() {

    printInOrderPrivate(root);

}

void BST::printInOrderPrivate(node * n) {

    if (n != NULL) {

        if (n->left != NULL) {
            printInOrderPrivate(n->left);
        }
        cout << n->data << " ";

        if (n->right != NULL) {
            printInOrderPrivate(n->right);
        }


    }

    else {
        cout << "The list is empty\n";
    }


}

Upvotes: 1

Views: 118

Answers (1)

Sani Huttunen
Sani Huttunen

Reputation: 24385

else if (data > root->data) { // add recursively on right left side.

should be 

else if (data > n->data) { // add recursively on right left side.

The problems start when you come to 32. Since 21 is already left of 50, your algorithm thinks it's already inserted 32, when you do root->data instead of the correct n->data, instead of comparing the data values and throwing an exception.

So: Check right and left for null, compare if data is greater or less AND check for equality. Doing so lets you more easily find bugs like this.

Upvotes: 4

Related Questions