3
\$\begingroup\$

I made binary search tree using classes. I would like to know if I could do something better or maybe there is something wrong with my code. I decided not to use recursion. I would be very thankful for any suggestions.

#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;



class Bst
{
private:
    struct BstNode
    {
        int data;
        BstNode* left;
        BstNode* right;
    };
public:
    Bst()
    {
        root = nullptr;
    }
    BstNode* insert(int data)
    {
        BstNode* newNode = new BstNode();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    bool add(int number)
    {
        if (root == nullptr)
        {
            root = insert(number);
        }
        else
        {
            BstNode* tmp_root = root;
            while (tmp_root != nullptr)
            {
                if (number <= tmp_root->data)
                {
                    if (tmp_root->left == nullptr)
                    {
                        tmp_root->left = insert(number);
                        return true;
                    }
                    else
                    {
                        tmp_root = tmp_root->left;
                    }
                }
                else
                {
                    if (tmp_root->right == nullptr)
                    {
                        tmp_root->right = insert(number);
                        return true;
                    }
                    else
                    {
                        tmp_root = tmp_root->right;
                    }

                }
            }
        }
        return false;
    }
    bool search(int number)
    {
        BstNode* tmp_root = root;
        while (tmp_root != nullptr)
        {
            if (number == tmp_root->data) return true;
            if (number < tmp_root->data)
            {
                tmp_root = tmp_root->left;
                continue;
            }
            if (number > tmp_root->data)
            {
                tmp_root = tmp_root->right;
            }
        }
        return false;
    }

private:
    BstNode* root;
};

int main()
{
    Bst tree;
    tree.add(10);
    tree.add(15);
    tree.add(2);
    tree.add(4);
    tree.add(7);
    for (int i = 1; i <= 20; i++)
    {
        string exist = tree.search(i) ? "YES" : "NO";
        cout << i << ": " << exist << endl;
    }
    system("pause");
    return 0;
}
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

You Break the Rule of Three/Five

{
    Bst  tree1;
    tree1.add(5);
    tree1.add(6);

    Bst  tree2(tree1);  // You just made a copy.
                        // Even though there is no copy constructor!

    tree2.add(8);       // both trees have 8 in them!!!!
}

Both trees are a mirror of each other. Adding nodes to one also adds nodes to the other. Also if you add the appropriate clean up code this will cause a break.

This is all caused because the compiler generates a couple of methods automatically. These methods work perfectly most of the time. But if your class contains an "Owned" RAW pointer then it does not work like you would expect.

So the simplest solution is to disable these auto-generated methods. You can then fix them later when you understand what is going on (look up rule of three).

    // Add this to your class.
    Bst(Bst const&)            = delete;
    Bst(Bst&&)                 = delete;
    Bst& operator=(Bst const&) = delete;
    Bst& operator=(Bst&&)      = delete;

Your class Leaks

For every call to new there must be a corresponding call to delete

    BstNode* newNode = new BstNode();

I don't see any calls to delete in your code. I don't see a destructor in your code to handle the clean up. So Add a destructor that deletes the tree from the root down.

Interface

The insert function:

BstNode* insert(int data)

looks out of place for a public function. This looks like an internal function that is called when you know where to insert the data value. Best to just make this private.

Simlify your Code

    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;

This can be replaced with a single line:

    return new BstNode{data, nullptr, nullptr};

Finding the node to insert a value:

    // Personally I would write this using recursion.
    // Its a balanced tree the chance of blowing the stack are small.
    BstNode*& find(BstNode*& node, int value)
    {
        if (node == nullptr) {
            return node;
        }
        return (node->value <= value)
                  ? find(node->left,  value)
                  : find(node->right, value);
    }

    // But if you must implement it using a loop then
    // its not much harder to write (you just need to handle
    // pointers to pointers). But it does make slightly harder
    // to read (Which is why I prefer the recursion route).
    BstNode*& find(BstNode*& node, int value)
    {
        BstNode** loop = &node;
        while(*loop != nullptr) {
            loop = (*loop)->value <= value
                  ? &((*loop)->left)
                  : &((*loop)->right);
        }
        return *loop;
    }

    void add(int value)
    {
        BstNode*&  nodeToModifiy = find(root, value);
        nodeToModifiy = insert(value);
    }
\$\endgroup\$
0
4
\$\begingroup\$

For simple projects like this, avoid #include "stdafx.h": it unnecessarily ties your code to Visual Studio.

Also avoid using namespace std;: it defeats all the the benefits of namespacing.

For readability, place at least one blank line between method definitions.


The biggest problem I see is your insert(data) method. It doesn't actually insert anything, as its name suggests. Rather, it allocates and initializes a BstNode. So, why not write that as a constructor, the way it should be?

struct BstNode
{
    int data;
    BstNode* left;
    BstNode* right;

    BstNode(int number) : data(number)
                        , left(nullptr)
                        , right(nullptr)
    {
    }
};

Then, you can write root = new BstNode(number);.

Similarly, the way you implement the Bst constructor is not idiomatic. You should use an initializer instead of a statement:

Bst() : root(nullptr)
{
}
\$\endgroup\$
2
  • \$\begingroup\$ I would avoid writing an explicit constructor for a simple class like this. I would rather use the implicit constructor that can be accessed via {} (don't know it official name yet). => new BstNode{number, nullptr, nullptr} \$\endgroup\$ Aug 21, 2017 at 22:18
  • \$\begingroup\$ @LokiAstari, its aggregate initializer \$\endgroup\$ Aug 22, 2017 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.