3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ The code in search is broken for a number of reasons. This question is off-topic because it can't work in many situations. You might want to enable warning messages in your compile, the warning I got was 'BstNode::Search': not all control paths return a value. \$\endgroup\$ – pacmaninbw Feb 23 at 22:04
  • \$\begingroup\$ @pacmaninbw I used onlineGDB and it compiled without any issues. Can you please tell what you're using so that I can try to reproduce the error? \$\endgroup\$ – Nothing_8484 Feb 23 at 22:13
  • \$\begingroup\$ I'm using Visual Studio 2019 installed locally on my computer. \$\endgroup\$ – pacmaninbw Feb 23 at 22:15
  • \$\begingroup\$ @pacmaninbw corrected the code. \$\endgroup\$ – Nothing_8484 Feb 23 at 22:52
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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