Skip to main content
Source Link
Loki Astari
  • 96.6k
  • 5
  • 125
  • 338

###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.

http://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));
}