Binary Search Tree C++

Question

Appreciate your thoughts and feedback...

BST.h

//
//  BST.h
//  BST
//
//  
//
//

#ifndef BST_h
#define BST_h

//  includes
#include <memory>
#include <string>
#include <iostream>


namespace bst {

template<class Key, class Data>
class BST
{
public:

    //
    //  Node
    //

    class Node {
    public:
        Node(const Key& k, const Data& d, Node* p)
        : key(k)
        , data(d)
        , left(nullptr)
        , right(nullptr)
        , parent(p) {}

        Node(const Key& k, const Data& d, std::unique_ptr<Node>& l, std::unique_ptr<Node>& r, Node* p)
        : key(k)
        , data(d)
        , left(std::move(l))
        , right(std::move(r))
        , parent(p) {}

        const Key& GetKey() const { return key; }
        Key& GetKey() { return key; }
        const Data& GetData() const { return data; }
        Data& GetData() { return data; }
        std::unique_ptr<Node>& GetLeft() { return left; }
        const std::unique_ptr<Node>& GetLeft() const { return left; }
        std::unique_ptr<Node>& GetRight() { return right; }
        const std::unique_ptr<Node>& GetRight() const { return right; }
        Node* GetParent() { return parent; }
        const Node* GetParent() const { return parent; }

        void SetLeft(std::unique_ptr<Node>& l) { left = std::move(l); }
        void SetRight(std::unique_ptr<Node>& r) { right = std::move(r); }
        void SetParent(Node* p) { parent = p; }
        void SetData(const Data& d) { data = d; }

    private:
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
        Node* parent;
        Key key;
        Data data;
    };

    //
    //  BST
    //

    BST()
    : root(nullptr) {}

    void Insert(const Key& k, const Data& d);
    void Remove(const Key& k);
    void Print(std::ostream& os);

private:
    void InsertHelper(std::unique_ptr<Node>& node, const Key& k, const Data& d);
    void RemoveHelper(std::unique_ptr<Node>& node, const Key& k);
    void PrintHelper(std::ostream& os, std::unique_ptr<Node>& node);


private:
    std::unique_ptr<Node> root;

};  //  BST

}  //  bst


template<class Key, class Data>
void bst::BST<Key,Data>::Remove(const Key& k)
{
    if(root) {
        RemoveHelper(root, k);
    } else {
        //  empty tree
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::RemoveHelper(std::unique_ptr<Node>& node, const Key& k)
{
    if(node->GetKey() == k) {
        //  found

        if(node->GetRight() && node->GetLeft()) {
            //  2 child
            //  swap with left child
            //  call function with new left child

            //  make a copy of left
            std::unique_ptr<Node> leftLeft = std::move(node->GetLeft()->GetLeft());
            std::unique_ptr<Node> leftRight = std::move(node->GetLeft()->GetRight());

            //  make a copy of node
            std::unique_ptr<Node> left = std::move(node->GetLeft());
            std::unique_ptr<Node> nodeRight = std::move(node->GetRight());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(left.get());
            node->SetRight(leftRight);
            node->SetLeft(leftLeft);

            //  setup left
            left->SetParent(nodeParent);
            left->SetLeft(node);
            left->SetRight(nodeRight);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent) {
                    nodeParent->SetRight(left);
                    RemoveHelper(nodeParent->GetRight(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(left);
                    RemoveHelper(nodeParent->GetLeft()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            }
        } else if(node->GetRight()) {
            //  1 child
            //  make a copy of left
            std::unique_ptr<Node> rightLeft = std::move(node->GetRight()->GetLeft());
            std::unique_ptr<Node> rightRight = std::move(node->GetRight()->GetRight());

            //  make a copy of node
            std::unique_ptr<Node> right = std::move(node->GetRight());
            std::unique_ptr<Node> nodeLeft = std::move(node->GetLeft());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(right.get());
            node->SetRight(rightRight);
            node->SetLeft(rightLeft);

            //  setup left
            right->SetParent(nodeParent);
            right->SetRight(node);
            right->SetLeft(nodeLeft);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent) {
                    nodeParent->SetRight(right);
                    RemoveHelper(nodeParent->GetRight()->GetRight(), k);
                } else {
                    root = std::move(right);
                    RemoveHelper(root->GetRight(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(right);
                    RemoveHelper(nodeParent->GetLeft()->GetRight(), k);
                } else {
                    root = std::move(right);
                    RemoveHelper(root->GetRight(), k);
                }
            }
        } else if(node->GetLeft()) {
            //  1 child
            //  make a copy of left
            std::unique_ptr<Node> leftLeft = std::move(node->GetLeft()->GetLeft());
            std::unique_ptr<Node> leftRight = std::move(node->GetLeft()->GetRight());


            //  make a copy of node
            std::unique_ptr<Node> left = std::move(node->GetLeft());
            std::unique_ptr<Node> nodeRight = std::move(node->GetRight());
            Node* nodeParent = node->GetParent();

            bool isRightChild = false;
            if(nodeParent && nodeParent->GetRight() == node) {
                isRightChild = true;
            }

            //  setup node
            node->SetParent(left.get());
            node->SetRight(leftRight);
            node->SetLeft(leftLeft);

            //  setup left
            left->SetParent(nodeParent);
            left->SetLeft(node);
            left->SetRight(nodeRight);

            //  connect left to parent
            //  and recursively call
            if(isRightChild) {
                if(nodeParent){
                    nodeParent->SetRight(left);
                    RemoveHelper(nodeParent->GetRight()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            } else {
                if(nodeParent) {
                    nodeParent->SetLeft(left);
                    RemoveHelper(nodeParent->GetLeft()->GetLeft(), k);
                } else {
                    root = std::move(left);
                    RemoveHelper(root->GetLeft(), k);
                }
            }
        } else {
            //  leaf
            //  remove
            node.reset();
        }
    } else if(node->GetRight() && node->GetRight()->GetKey() < k) {
        RemoveHelper(node->GetRight(), k);
    } else if(node->GetLeft() && node->GetLeft()->GetKey() > k) {
        RemoveHelper(node->GetLeft(), k);
    } else {
        //  not found
    }
}


template<class Key, class Data>
void bst::BST<Key,Data>::Insert(const Key& k, const Data& d)
{
    if(root) {
        InsertHelper(root, k, d);
    } else {
        root = std::unique_ptr<Node>(new Node(k,d, nullptr));
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::InsertHelper(std::unique_ptr<Node>& node, const Key& k, const Data& d)
{
    if(node->GetKey() < k) {
        //  insert into right subtree

        //  first check there is a right subtree
        if(node->GetRight()) {
            //  recursivley traverse the right subtree
            InsertHelper(node->GetRight(), k, d);
        } else {
            //  no right subtree?
            //  then insert item as right child
            std::unique_ptr<Node> tempNode(new Node(k,d, node.get()));
            node->SetRight(tempNode);
        }
    } else if(node->GetKey() > k) {
        //  insert into left subtree

        //  first check there is a left subtree
        if(node->GetLeft()) {
            //  recursivley traverse the left subtree
            InsertHelper(node->GetLeft(), k, d);
        } else {
            //  no left subtree?
            //  then insert item as left child
            std::unique_ptr<Node> tempNode(new Node(k,d, node.get()));
            node->SetLeft(tempNode);
        }
    } else {
        //  found
        //  insert here
        node->SetData(d);
    }
}

template<class Key, class Data>
void bst::BST<Key,Data>::Print(std::ostream& os)
{
    if(!root) {
        PrintHelper(os, root);
    }
}


template<class Key, class Data>
void bst::BST<Key,Data>::PrintHelper(std::ostream& os, std::unique_ptr<Node>& node)
{
    //  print key
    os << "Key: " << node->GetKey() << std::endl;

    if(node->GetLeft()) {
        os << "Left: " << node->GetLeft()->GetKey() << std::endl;
    } else {
        os << "Left: null" << std::endl;
    }

    if(node->GetRight()) {
        os << "Right: " << node->GetRight()->GetKey() << std::endl;
    } else {
        os << "Right: null" << std::endl;
    }

    os << std::endl;

    if(node->GetLeft()) {
        PrintHelper(os, node->GetLeft());
    }

    if(node->GetRight()) {
        PrintHelper(os, node->GetRight());
    }
}


#endif /* BST_h */

main.cpp

//
//  main.cpp
//  BST
//
//  
//
//

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

int main(int argc, const char * argv[]) {


    bst::BST<int,int> bst1;
    bst1.Insert(6, 6);
    bst1.Insert(4, 4);
    bst1.Insert(8, 8);

    bst1.Insert(3, 3);
    bst1.Insert(5, 5);

    bst1.Insert(7, 7);
    bst1.Insert(9, 9);

    bst1.Print(std::cout);

    bst1.Remove(6);

    bst1.Print(std::cout);

    // insert code here...
    std::cout << "Hello, World!\n";

    std::cin.get();

    return 0;
}

I have added the code to github here

Am using a unique pointer to manager memory. Each node owns its left and right child. Can only move a child node.

Answer 1

Code Review

Its traditional that macros are all upper case.

#ifndef BST_h
#define BST_h

Also that is a bit short. When I do this I usually add the namespace of the code as part of the guard. Also You want to make the namespace unique (so it will never clash, I use the name of a domain I own you could use SRG?). Other naming conventions you should look out for. User defined types usually have an initial capitol letter and objects and functions usually have an initial lowercase letter. Personally I also Initialize the first letter in a namespace but that is very random.

I would have done something like this:

#ifndef  SRG_TREE_BST_H
#define  SRG_TREE_BST_H

namespace SRG::Tree {
    class BST {
        // STUFF
    };
}
#endif

The compiler should have generated a warning about this.

        Node(const Key& k, const Data& d, Node* p)
        : key(k)
        , data(d)
        , left(nullptr)
        , right(nullptr)
        , parent(p) {}

The order of this list is not important. The order the members are initialized in is the order they are declared in below. The compiler should warn you that the two orders are not the same. The reason the compiler warns you is that on more complex classes this can be important (the order of member initialization) and this false impression you are giving the reader may confuse them. So always make the initialization list the same order as the order of declaration.

Secondary note. As this compiles for you this means you are not treating errors as warnings. Go back to your compiler and turn UP the warning level as high as it will go. Then set the compiler to treat warnings as errors. Each warning is a logical error in your thinking. All new code should compile with zero warnings.

Getters/Setters break encapsulation and expose the internal types of the class. They are generally considered a bad thing in C++. They are liked a lot in Java because a lot of tools use them.

In C++ we prefer action() methods that modify the class, rather than get(), perform action, set() as this leaks the functionality of the class to external objects.

In this case your Node is a simply property bag. The only class with accesses is the bst so just make the members public and allow the tree to efficiently manipulate them.

        const Key& GetKey() const { return key; }
        Key& GetKey() { return key; }
        const Data& GetData() const { return data; }
        Data& GetData() { return data; }
        std::unique_ptr<Node>& GetLeft() { return left; }
        const std::unique_ptr<Node>& GetLeft() const { return left; }
        std::unique_ptr<Node>& GetRight() { return right; }
        const std::unique_ptr<Node>& GetRight() const { return right; }
        Node* GetParent() { return parent; }
        const Node* GetParent() const { return parent; }

        void SetLeft(std::unique_ptr<Node>& l) { left = std::move(l); }
        void SetRight(std::unique_ptr<Node>& r) { right = std::move(r); }
        void SetParent(Node* p) { parent = p; }
        void SetData(const Data& d) { data = d; }

Sure you can use smart pointers here.

        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;

Personally I think the tree could handle this. But I can't really complain about the usage. So this is just a personal comment.

The parent. Hmmm.

        Node* parent;

I think you will find that keeping track of the parent node will make the code harder to write. But lets see!

Sure this is a find method to have:

    void Print(std::ostream& os); // should this not be const???

But in C++ printing is usually done via operator<<. So you should also define this (it can call Print).

    friend std::ostream& operator<<(std::ostream& s, bst const& t) {
        t.Print(s);
        return s;
    }

Don't leave empty blocks lying around the code.

    if(root) {
        RemoveHelper(root, k);
    } else {
        //  empty tree              // Useless comment delete this block.
    }

There is a helper function to make unique_ptr objects: std::make_unique().

    if(root) {
        InsertHelper(root, k, d);
    } else {
        // root = std::unique_ptr<Node>(new Node(k,d, nullptr));
        root = std::make_unique<Node>(k, d, nullptr);
    }

Ahh printing and recursion.

In all the other places were you have a nullptr. You print null, but not for the root node. Which means an empty tree prints nothing. This seems a bit inconsistent. I would make it print null for the empty tree.

Also you are not passing ownership around. So don't pass the smart pointer. Pass a pointer to the object (normally I would say reference but in this case we can have nullptr).

    if(!root) {
        PrintHelper(os, root);
    }

Recursion. You can make your recursion much simpler. The first thing you do is check if you have fallen off then end. If so return (and you can print null). Then you can do all your printing work knowing that you are in a valid node.

Also prefer "\n" over std::endl. The difference between the two is simply that std::endl will force the buffer to flush (which makes the stream very inefficient). Manual flushing is nearly always the wrong thing to do and the cause of most slowdowns in streaming code.

So I would rewrite your print like this:

template<class Key, class Data>
void bst::BST<Key,Data>::Print(std::ostream& os)
{
    PrintHelper(os, root.get());
}


template<class Key, class Data>
void bst::BST<Key,Data>::PrintHelper(std::ostream& os, Node* node)
{
    if (node == nullptr) {
        os << "null\n";
    }

    //  print key
    os << "Key: " << node->GetKey() << "\n"
       << "Left:  (" << node->GetLeft().get() << ")\n"
       << ", Right: (" << node->GetRight().get() << ")\n;        
}

These last two are huge functions. Way bigger than they should be (I am betting that is to keep the parent member in line correctly. I have not had time to digg into them and find the problem yet. But I will come back tonight.

But lines like this scare me:

            //  make a copy of node
            std::unique_ptr<Node> left = std::move(node->GetLeft());
            std::unique_ptr<Node> nodeRight = std::move(node->GetRight());

Nope. You are not making a copy. You just moved the pointers. Comments that are out of sync with the code are WORSE then useless comments. Do you want me to believe the comment (you are making a copy) are do I believe the code (you are moving the pointers). Did you believe you were making a copy and that assumption cause the code below to break? I don't know. As a maintainer I would hate you as now I would need to debug your code to make sure you did it correctly then fix your code or your comment.

Insert Helper

My first though about this. Is that if the key already exists then its not inserting the data (we are overwriting the existing data). Now this could be OK but it would be nice to know. If we look at the standard containers an insert into std::map returns a boolean indicating if an insert happened (true data was inserted, false data was not inserted but the data is in the map).

The rest goes back to standard recursion. You can remove half the rest of the code. By not checking if the left/right are null but just re-calling InsertHelper() and retuning the new value. If the value is null on entrance you create the value and return it.

// This is how I would write it.
// Slightly different as I would use pointers not smart pointers
// But I am sure you can modify to copensate.
Node* bst::BST<Key,Data>::InsertHelper(Node* node, const Key& k, const Data& d)
{
    // When you fall off the end
    // Then create the node and return it.
    if (node == nullptr) {
        return new Node(k, d, nullptr);
    }

    if (k < node->key) {
        node->left = InsertHelper(node->left, k, d);
    }
    else if (k > node->key) {
        node->right = InsertHelper(node->right, k, d);
    }
    else {
        node->data = d;
    }
    // If you did not fall of the end.
    // Then return the node as the result so it sets itself back.
    return node;
}

Remove Helper

One thing I would note is that you don't normally pass unique_ptr by reference.

void bst::BST<Key,Data>::PrintHelper(std::ostream& os, std::unique_ptr<Node>& node);

If the interface takes a unique_ptr by reference you can tell if it is taking ownership or not. When you pass a unique_ptr to an interface the parameter is normally a value parameter this forcing you to use std::move() to transfer ownership. I suppose in this case it might be OK as you don't know if you are going to take ownership but the use case worries me a bit.

This is way to long with way to many special cases.

It should look like this:

// This is how I would write it.
// Slightly different as I would use pointers not smart pointers
// But I am sure you can modify to copensate.
Node* bst::BST<Key,Data>::RemoveHelper(Node* node, const Key& k)
{
    // When you fall off the end
    // the key was not found. So just return null.
    if (node == nullptr) {
        return nullptr;
    }


    // In most cases we return the current node.
    // So lets keep track of that separately. If this
    // is the node we are going to delete then we update
    // this with the node we are going to replace it with.
    Node* result = node;


    if (k < node->key) {
        // Note if we don't remove node-left then it will
        // return back the same value and nothing happens.
        // If we do delete node->left we will return the replacement value.
        // Note: In this case the node is not deleted so result is not changed.
        node->left = RemoveHelper(node->left, k);
    }
    else if (k > node->key) {
        // See comment above about left.
        node->right = RemoveHelper(node->right, k);
    }
    else {

        // We found the node we delete.
        // In here we must change `result` to reflect the new node.

        // If either of the sub-trees is empty this becomes easy as the other
        // sub-tree becomes the new current node.
        if (node->left == nullptr || node->right == nullptr) {
            result = node->left == nullptr ? node->right : node->left;
            delete node;
        }
        else {
            // OK both sub trees are not null.
            // We must find a node to be used here.
            // A node where all the nodes to the right are larger
            // and all the nodes to the left are smaller.
            //
            // If we look in the right sub-tree. Then the left most
            // node in this sub tree fulfills these requirements.
            // We can also easily remove it as it will not have a
            // left-subtree. Once we have it assign the 
            // left and right sub-trees of the current node to it
            // It will be inserted into the tree with the return
            // below.
            node->right = findLeftMostNode(node->right, result);
            result->left = node->left;
            result->right= node->right;
            delete node;
        }

    }
    // If you did not fall of the end.
    // Then return the result
    return result;
}

Node* findLeftMostNode(Node* node, Node*& result)
{
    if (node->left == nullptr) {
        // We found the left most node. So this is the result.
        result = node;
        // We return its right-subtree so that it can be glued
        // back into the BST.
        return node->right;
    }

    // We have not found the left most node.
    // So keep looking.
    node->left = findLeftMostNode(node->left, result);
    return node;
}