Simple Binary Search Tree Class with Insert and Search Functions

Question

I am trying to learn to implement DSs in C++ and here is a simple implementation. Please review in terms of optimization, memory management, coding standards, etc

#include <stdio.h>
#include <iostream>

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

public:
BstNode(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
~BstNode();

void Insert(int data)
{
    if(this->data >= data)
    {
        if (this->left == NULL)
            this->left = new BstNode(data);
        else 
            this->left->Insert(data);
    }
    else
    {
        if (this->right == NULL)
            this->right = new BstNode(data);
        else 
            this->right->Insert(data);
    }
}

bool Search(int data)
{
    if(this->data == data)
        return true;
    else if(this->data >= data)
    {
        if(this->left == NULL)
            return false;
        else
            return this->left->Search(data);
    }
    else
    {
        if(this->right == NULL)
            return false;
        else
            return this->right->Search(data);
    }

}
};

int main()
{
BstNode* ptr_root = new BstNode(15);
ptr_root->Insert(10);
ptr_root->Insert(16);
int num;
std::cout<<"Enter the number: \n";
std::cin>> num;
if (ptr_root->Search(num))
    std::cout<<"Found\n";
else
    std::cout<<"Not Found\n";

return 0;
}

Answer 1

Overall organization

Right now, you've defined a BstNode, which you use directly in main. I'd at least consider defining a Bst class, and then (probably inside that) a Node class.

class Bst {
    class Node {
        // only code to deal with individual nodes goes here
    };

    Node *root;
public:

    bool insert(int value);

    bool find(int value);
};

Then to create a Binary search tree, you'd just instantiate a Bst object, and use it:

int main() {

    Bst tree;

    // oops--this will lead to a completely imbalanced tree.
    for (int i=0; i<10; i++)
        tree.insert(i);

}

in-class initialization

Since you (almost?) always create a node with its child pointers set to nullptrs, I'd just specify that directly in the class instead of in the ctor:

// ...
class Node {
    int value;
    Node *left = nullptr;
    Node *right = nullptr;

    Node(int value) : value(value) {}
};

Insertion and Search

I'd at least consider whether you really want to use recursion to do insertion and/or search. Since you only ever descend to one child of any given node, it's pretty easy to use iteration for these tasks.

Insert return type

I'd at least consider having Insert return a bool to indicate whether it actually inserted a value in the tree or not (e.g., return false if a value is already present).

Collection type

What you've currently implemented is roughly equivalent to a std::set. That is, it stores only keys. This can certainly be useful, but there are times its also useful to have data associated with the key (i.e., roughly equivalent to std::map).

Generic Code

Right now, you've written the code so the only thing can be stored in your BST is ints. I'd at least consider making it generic so other types can be stored.

template <class T, class Cmp = std::less<T>>
class Bst {
    // ...

This increases complexity a little, but increases functionality quite a lot.

Answer 2

This program is using purely C++ I/O so the include for the old style C I/O is not necessary, you don't need the #include <stdio.h> and it would be better to remove it.

The indentation of the code is inconsistent and confusing, both in the class and in the main() function.

Generally in C++ it is unnecessary to use the this pointer, it is required in only two places in the code and wouldn't be necessary at all if the name of the input variable was changed.

    BstNode(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }


    bool Search(int data)
    {
        if(this->data == data)
            return true;
        else if(data >= data)
        {
            if(left == nullptr)
                return false;
            else
                return left->Search(data);
        }
        else
        {
            if(right == nullptr)
                return false;
            else
                return right->Search(data);
        }

    }

In modern C++ one should use nullptr rather than NULL as shown above.