C++ binary search tree, not using recursion 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 &lt;iostream&gt;
#include &lt;string&gt;

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-&gt;data = data;
        newNode-&gt;left = nullptr;
        newNode-&gt;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 &lt;= tmp_root-&gt;data)
                {
                    if (tmp_root-&gt;left == nullptr)
                    {
                        tmp_root-&gt;left = insert(number);
                        return true;
                    }
                    else
                    {
                        tmp_root = tmp_root-&gt;left;
                    }
                }
                else
                {
                    if (tmp_root-&gt;right == nullptr)
                    {
                        tmp_root-&gt;right = insert(number);
                        return true;
                    }
                    else
                    {
                        tmp_root = tmp_root-&gt;right;
                    }

                }
            }
        }
        return false;
    }
    bool search(int number)
    {
        BstNode* tmp_root = root;
        while (tmp_root != nullptr)
        {
            if (number == tmp_root-&gt;data) return true;
            if (number &lt; tmp_root-&gt;data)
            {
                tmp_root = tmp_root-&gt;left;
                continue;
            }
            if (number &gt; tmp_root-&gt;data)
            {
                tmp_root = tmp_root-&gt;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 &lt;= 20; i++)
    {
        string exist = tree.search(i) ? "YES" : "NO";
        cout &lt;&lt; i &lt;&lt; ": " &lt;&lt; exist &lt;&lt; endl;
    }
    system("pause");
    return 0;
}
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&amp;)            = delete;
    Bst(Bst&amp;&amp;)                 = delete;
    Bst&amp; operator=(Bst const&amp;) = delete;
    Bst&amp; operator=(Bst&amp;&amp;)      = 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-&gt;data = data;
    newNode-&gt;left = nullptr;
    newNode-&gt;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*&amp; find(BstNode*&amp; node, int value)
    {
        if (node == nullptr) {
            return node;
        }
        return (node-&gt;value &lt;= value)
                  ? find(node-&gt;left,  value)
                  : find(node-&gt;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*&amp; find(BstNode*&amp; node, int value)
    {
        BstNode** loop = &amp;node;
        while(*loop != nullptr) {
            loop = (*loop)-&gt;value &lt;= value
                  ? &amp;((*loop)-&gt;left)
                  : &amp;((*loop)-&gt;right);
        }
        return *loop;
    }

    void add(int value)
    {
        BstNode*&amp;  nodeToModifiy = find(root, value);
        nodeToModifiy = insert(value);
    }