C++ binary search tree

Question

I am learning C++ and today I've implemented a version of the binary search tree. I would like your thoughts about it.

node.h

#pragma once

struct Node
{
   int val;
   Node *left;
   Node *right;
};

bTree.h

#include "node.h"

#pragma once

class BTree
{
private:

    Node *root;
    void addValue(int n, Node *node);
    void traverse(Node *node);
    Node* search(int n, Node *node);

public:

    BTree();

    void addValue(int n);
    void traverse();
    void search(int n);
};

bTree.cpp

#include <iostream>
#include "bTree.h"

BTree::BTree()
{
    root = nullptr;
}

void BTree::addValue(int n, Node *node) {
    if (n < node->val)
    {
        if (node->left != nullptr)
        {
            addValue(n, node->left);
        }
        else
        {
            node->left = new Node;
            node->left->val = n;
            node->left->left = nullptr;
            node->left->right = nullptr;
        }
    }
    else if (n >= node->val)
    {
        if (node->right != nullptr)
        {
            addValue(n, node->right);
        }
        else
        {
            node->right = new Node;
            node->right->val = n;
            node->right->left = nullptr;
            node->right->right = nullptr;
        }

    }
}

void BTree::traverse(Node *node) {
    if (node->left != nullptr)
        traverse(node->left);
    std::cout << node->val << ' ';
    if (node->right != nullptr)
        traverse(node->right);
}

Node* BTree::search(int n, Node *node) {
    if (node != nullptr)
    {
        if (node->val == n)
            return node;
        else if (n < node->val)
            return search(n, node->left);
        else if (n > node->val)
            return search(n, node->right);
    }
    else
        return nullptr;
}

void BTree::addValue(int n) {
    if (root == nullptr)
    {
        root = new Node;
        root->val = n;
        root->left = nullptr;
        root->right = nullptr;
    }
    else
    {
        addValue(n, root);
    }
}

void BTree::traverse() {
    if (root == nullptr)
    {
        std::cout << "No nodes in the tree" << std::endl;
    }
    else
    {
        traverse(root);
    }
}
void BTree::search(int n) {
    if (root == nullptr)
    {
        std::cout << "No nodes in the tree" << std::endl;
    }
    else
    {
        if (search(n, root))
            std::cout << n << " found" << std::endl;
        else
            std::cout << n << " not found" << std::endl;
    }
}

main.cpp

#include <iostream>
#include "bTree.h"
#include <ctime>

int main()
{
    srand(static_cast<unsigned int>(time(0)));
    rand();

    BTree bTree{};

    for (int i = 0; i < 50; i++)
    {
        int n = rand() % 100;
        std::cout << n  << ' ';
        bTree.addValue(n);
    }

    std::cout << std::endl << std::endl;

    bTree.traverse();

    std::cout << std::endl << std::endl;

    for (int i = 0; i < 10; i++)
    {
        int n = rand() % 100;
        bTree.search(n);
    }

    std::cout << std::endl << std::endl;

    system("pause");

    return 0;
}

Answer 1

Use constructors to initialize your objects.

        root = new Node;
        root->val = n;
        root->left = nullptr;
        root->right = nullptr;

This should be replaced by:

        root = new Node(n);

Design

I think you will find that your code becomes a lot simpler if you move your test for null out of the public members. Then make the test for null the first thing you do in the private member (Don't test before you call the private member test as the first action in the call). This will simplify all the situations were you currently have to test for null.

For Example:
I would write addValue like this:

void BTree::addValue(int n) {
    root = addValue(n, root);
}
Node* BTree::addValue(int n, Node* current) {
    if (current == nullptr) {
        return new Node(n);
    }
    if (n < current->val) {
        current->left  = addValue(n, current->left);
    else if (n > current->val) {
        current->right = addValue(n, current->right);
    }
    return current;
}

Answer 2

1) I advise you to keep common includes together and separated from your program includes - might be handy once there are enough of them.

#include <ctime>
#include <iostream>

#include "bTree.h"

2) I suggest you change the name of your class, because it looks pretty much like B-Tree, which is different (e.g. self-balancing).

3) The next thought is that binary search tree would benefit a lot if it were templated, not hard-coded on int values. Little upgrade on the code, significant boost in usability.

These are all minor thoughts, the most important part was already mentioned by Loki Astari.

Answer 3

Then working with pointers ad dynamic memory, there is always an important question of ownership. Who owns the nodes? Who is responsible of deleting them? (Remember, C++ does not have an automatic garbage collection, and freeing memory must be handled manually or by using containers or smart pointers)

Currently your code allocates nodes with new but does not delete them. The nodes are left in memory after the user of your tree is done with it. This is called memory leak. The best way to avoid it is to add a destructor where you traverse the tree and delete all the nodes.