C++ binary search tree with templates

Question

I implemented a binary search tree with methods of insert, search, size and print using the << operator. All the methods works with template. main is a simple demonstration of the methods and templates working correctly. Please also review the code formatting.

Node.h

#pragma once
#ifndef Node_h
#define Node_h

template < class T >
class Node
{
    public :

        Node ( T val ) : m_val( val ) , m_left( nullptr ) , m_right( nullptr ){}

        T m_val;
        Node<T> *m_left; 
        Node<T> *m_right; 

};
#endif

BST.h

#ifndef BST_h
#define BST_h
#include "Node.h"
#include <iostream>

template < class T >
class BST;

template < class T >
 std::ostream &operator<< ( std::ostream &os , const BST<T> &current ) ;


template < class T >
class BST
{
    public :
        BST  ();
        ~BST ();

        void insertBST  ( const T &val );
        void insertBST  ( Node <T>*cuurent , const T &val );

        void destroyBST ( Node <T>*current );

        bool searchVal  ( const T &val ) const;
        bool searchVal  (  Node<T> *current , const T &val ) const;

        int  sizeBST    ( ) const;
        int  sizeBST    ( const Node <T> *current ) const;

        void inorderBST () const ; 
        void inorderBST ( const Node <T>*current ) const; 

        friend std::ostream &operator<< <>( std::ostream &os , const BST &current ) ;

    private :
        Node <T>*m_root;

};


template < class T >    
 std::ostream &operator<< ( std::ostream &os , const BST<T> &current ) 
    {
        current.inorderBST();
        return os;
    }


template < class T >
BST<T>::BST ()
    {
        m_root = nullptr;
    }



template < class T >
BST<T>::~BST ()
    {
        destroyBST( m_root ); 
        delete m_root;
    }



template < typename T >
void BST<T>::insertBST ( Node <T>*current , const T &val )
{   
    if ( current->m_val > val )
        {
            if( current->m_left == nullptr )
                {
                    current->m_left = new Node<T>( val );
                }
            else
                {
                    insertBST( current->m_left , val );
                }
        }
    else
    {
        if( current->m_right == nullptr )
            {
                    current->m_right = new Node<T>( val );
            }
            else
                {
                    insertBST( current->m_right , val );
                }
    }
}



template < typename T >
void BST<T>::insertBST ( const T &val )
    {
        if ( m_root == nullptr )
            {
                m_root = new Node<T>( val );
            }
        else
            {
                        insertBST( m_root , val );
            }
    }



template < typename T >
void BST<T>::destroyBST( Node <T>*current )
    {
        if ( current->m_left != nullptr )
            {
                destroyBST( current->m_left );
                delete current->m_left;
            }
        if ( current->m_right != nullptr )
            {
                destroyBST( current->m_right );
                delete current->m_right;
            }
    }



template < typename T >
bool BST<T>::searchVal ( const T &val ) const
    {   
        bool b ; 
        if ( m_root == nullptr)
            {
                return false;
            }
        else
            {
                 b = searchVal(m_root,val);     
            }
        return b ; 
    }



template < typename T >
bool BST<T>::searchVal ( Node <T> *current, const T &val ) const
    {
        if( current->m_val == val )
            {
                return true ;
            }
        else
            {
                bool right , left ; 
                right = left = false;
                if ( current->m_right != nullptr )
                    {
                        right = searchVal( current->m_right , val );
                    }
                if ( current->m_left != nullptr )
                    {
                        left = searchVal( current->m_left , val );
                    }
                if ( right || left )
                    {
                        return true;
                    }
                else
                    {
                        return false ; 
                    }
            }

    }


template < typename T >
int  BST<T>::sizeBST () const
    {
        if( m_root == nullptr )
            {
                return -1 ;
            }
        else
            {
                return ( sizeBST ( m_root ) );
            }

    }



template < typename T >
int  BST<T>::sizeBST ( const Node <T> *current ) const
    {
        if ( current == nullptr )
            {
                return 0 ; 
            }
        int left , right ; 
        left = sizeBST(current->m_left);
        right = sizeBST(current->m_right);
        return ( left > right ? left + 1 : right + 1 );

    }


template < typename T >
void BST<T>::inorderBST () const
    {
        if ( m_root == nullptr ) 
            {   
                std::cout <<"The tree is empty \n" ; 
            }
        else
            { 
                inorderBST ( m_root );
                std::cout<<"\n";
            }
    }



template < typename T >
void BST<T>::inorderBST ( const Node <T> *current ) const
    {
        if ( current != nullptr )
            {
                inorderBST ( current->m_left );
                std::cout<< current->m_val << " " ;
                inorderBST ( current->m_right );
            }
    }

#endif

main.cpp

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

int main ()
{ 
    BST <int> testInt;
    int tempInt; 



    std::cout << "Please enter values to BST type int ( enter -1 to stop and print inorder and size) \n";
    std::cin >> tempInt;

    while ( tempInt != -1 )
        {
            testInt.insertBST( tempInt );
            std::cin >> tempInt;
        }

    std::cout << testInt ; 

    tempInt = testInt.sizeBST();
    std::cout << "Tree size is " << tempInt << "\n" ;

    std::cout << "Please enter value you want to search (enter -1 to stop)\n";
    std::cin >>tempInt;
    while ( tempInt != -1 )
    {
        bool tempSearch = testInt.searchVal( tempInt );
        if ( tempSearch)
            {
                std::cout << "The value exsit in the tree ! \n";
            }
        else
            {
                std::cout <<"The value does not exsit in the tree!\n";
            }
        std::cin >> tempInt;
    }
    std::cout <<"Congratulations you finished to check INT type lets check double \n";


    BST <double> testDouble;
    double tempDouble; 

    std::cout << "Please enter values to BST type double ( enter -1 to stop and print inorder and size) \n";
    std::cin >> tempDouble;

    while ( tempDouble != -1 )
        {
            testDouble.insertBST( tempDouble );
            std::cin >> tempDouble;
        }

    std::cout << testDouble ; 

    tempDouble = testDouble.sizeBST();
    std::cout << "Tree size is " << tempDouble << "\n" ;

    std::cout << "Please enter value you want to search (enter -1 to stop)\n";
    std::cin >>tempDouble;
    while ( tempDouble != -1 )
    {
        bool tempSearch = testDouble.searchVal( tempDouble );
        if ( tempSearch)
            {
                std::cout << "The value exsit in the tree ! \n";
            }
        else
            {
                std::cout <<"The value does not exsit in the tree!\n";
            }
        std::cin >> tempDouble;
    }

    std::cout <<"Congratulations you finished to check Double type \n";

    return  0; 
}

Answer 1

Private Node

Do you want to expose the Node class?

Personally I would make it a private member of the BST class. Then never expose it to the user. By exposing it you will need to maintain that class in perpetuity.

Also your BST class does not return a node pointer so it does not seem necessary to expose this type.

Rule of Three

You did not implement the rule of three. This is a common beginners mistake. Please look up the rule of three and then implement it (the easiest way is to disable copy semantics).

// Issue
BST<int>  x;
x. insertBST(1);
BST<iny>  y(x);   // compiler generated copy constructor
                  // will make a shallow copy of x. 
                  //
                  // Both objects root pointer point at the same thing. 
                  // Destructor will delete the object twice.

Move Semantics

You should implement move semantics. A copy of a big tree will either be expensive (if you implement the rule of three) or disabled. But a move is very cheap which will allow you to move a tree to a function or return it with a move from a function that builds the tree.

Emplace or Move Value

When you pass a value to your BST it must be copied into the tree when the Node is created. But you can move an object. This is usually much more efficient.

void insertBST  (T const&&  val);
                  //    ^^  binds an rvalue reference allowing a move

Emplace is an advanced form of move where you pass values that are required by the constructor of T so that the value can be constructed in place.

Interface

Only half of these methods need to be public.

public:
    void insertBST  ( const T &val );
    void insertBST  ( Node <T>*cuurent , const T &val );

    void destroyBST ( Node <T>*current );

    bool searchVal  ( const T &val ) const;
    bool searchVal  (  Node<T> *current , const T &val ) const;

    int  sizeBST    ( ) const;
    int  sizeBST    ( const Node <T> *current ) const;

    void inorderBST () const ; 
    void inorderBST ( const Node <T>*current ) const; 

I would divide these into a public interface and a private interface:

public:
    // These are the functions the user can call.
    void destroyBST ( Node <T>*current );

    void insertBST  ( const T &val );
    bool searchVal  ( const T &val ) const;
    int  sizeBST    ( ) const;
    void inorderBST () const ; 

private:
    // These are the functions that the public inteface calls
    // after getting private data. There is no way for the user
    // to call these methods as they can't get a `Node<T>` without
    // illegally creating their own.
    void insertBST  ( Node <T>*cuurent , const T &val );
    bool searchVal  (  Node<T> *current , const T &val ) const;
    int  sizeBST    ( const Node <T> *current ) const;
    void inorderBST ( const Node <T>*current ) const; 

Placement of `const

I prefer putting the const on the right.

The rule is const binds to the left unless it is on the very left hand side of the type then it binds right. In nearly all circumstances it makes no difference but there is one corner case where putting it on the left can get you unexpected results (but it is a rare corner case).

 But I think it makes reading types more logical when placed on the right. As the correct way to read types is right to left.

https://stackoverflow.com/a/7088806/14065 https://www.codeproject.com/Articles/7042/How-to-interpret-complex-C-C-declarations

But I think it makes reading types more logical when placed on the right. As the correct way to read types is right to left.

 void inorderBST ( const Node <T>*current ) const;

I would write as this:

 void inorderBST (Node <T> const*  current) const;

Simplify Your code

All your code can be highly simplified. The public interface should do nothing but call the private version and passing root. There is no need for any logic here.

You can also simplfy your code by checking current is null after the call rather than before the call.

void BST<T>::insertBST(T const&  val)
{
    root = insertBST(root, val);
}
void BST<T>::insertBST(Node<T>* current , T const& val)
{
    if (current == nullptr) {
        return new Node<T>(val);
    }

    if (current->m_val > val)
    {
        current->left = insertBST(current->left, val);
    }
    else
    {
        current->right = insertBST(current->right, val);
    }
    return current;
} 


bool BST<T>::searchVal(T const&  val) const
{
    return searchVal(root, current);
}

bool BST<T>::searchVal(Node<T>* current, T const& val) const
{
    if (current == nullptr) {
        return false;
    }
    if (current->m_val == val) {
        return true;
    }
    return searchVal(current->m_val > val ? current->left: current->right, val);
}


int  BST<T>::sizeBST() const
{
    return sizeBST(root);
}

int  BST<T>::sizeBST(Node <T> const* current) const
{
    if (current == nullptr) {
        return 0;
    }

    return 1+ std::max(sizeBST(current->m_left),
                       sizeBST(current->m_right));
}

Answer 2

You have a destructor but no sign of a copy constructor or copy assign (nor of the move variant), you should implement them or mark them deleted to avoid use-after-free bugs:

BST (const BST&)=delete;
BST& operator=(const BST&)=delete;