Binary Search Tree implementation in C++ with templates

Question

Im implementing a BST using templates and dynamic memory, here is my attempt:

This is the BSTNode.hh

#ifndef BSTNODE_HH
#define BSTNODE_HH

#include <list>
#include <algorithm>
using namespace std;

template <class K, class V>
class BSTNode
{
public:
    BSTNode(const K &key) {
        this->key = key;
        this->values = {};
    }

    BSTNode(const K &key, const list<V>& values) {
        this->key = key;
        this->values = values;
    }

    BSTNode(const BSTNode<K, V> &orig) 
    {
        this->key = orig.key;
        this->values = orig.values;
        if (orig.left != nullptr)
        {
            this->left = new BSTNode<K, V>(*orig.left);
            //this->left->setValues()
            left->setParent(this); // Goes back to the new child to set the parent as this
        }

        if (orig.right != nullptr)
        {
            this->right = new BSTNode<K, V>(*orig.right);
            right->setParent(this); // Goes back to the new child to set the parent as this
        }
    };

    virtual ~BSTNode() { }

    /* Modificadors */
    // Declareu-hi aquí els modificadors (setters) dels atributs que manquen
    /* Consultors */
    void setParent(BSTNode<K, V> *parent) { this->parent = parent; }
    void setRight(BSTNode<K,V> *right){this->right = right;}
    void setLeft(BSTNode<K,V>*left){this->left= left;}
    void setValues(const list<V>& v) {this->values = v;}
    
    // Declareu-hi aquí els consultors (getters) dels atributs que manquen
    const K &getKey() const { return key; }
    const list<V> &getValues() const { return this->values; }
    BSTNode<K, V>* getLeft() const {return this->left;}
    BSTNode<K, V>* getRight() const {return this->right;}
    BSTNode<K, V>* getParent() const {return this->parent;}

    /* Operacions */
    bool isRoot() const { return this->parent == nullptr; }
    bool hasLeft() const { return left != nullptr; }
    bool hasRight() const { return right != nullptr; }
    bool isExternal() const { return !hasLeft() and !hasRight(); }
    void insertValue(const V &v) { values.push_back(v); }
    int depth() const
    {
        if (this->isRoot())
            return 0;
        else
            return 1 + parent->depth();
    }

    int height() const
    {
        if (isExternal())
            return 1;
        else
            return 1 + max(left->height(), right->height());
    }
    
    bool operator==(const BSTNode<K, V> &node) const
    {
        if (key != node.key)
            return false;
        auto it1 = values.begin();
        auto it2 = node.values.begin();

        for (; it1 != values.end() && it2 != node.values.end(); it1++, it2++)
        {
            if (*it1 != *it2)
                return false;
        }

        return it1 == values.end() && it2 == node.values.end();
    }

private:
    K key;
    list<V> values;
    // Afegiu-hi aquí els atributs que manquen
    BSTNode<K, V> *left{nullptr};
    BSTNode<K, V> *right{nullptr};
    BSTNode<K, V> *parent{nullptr};
};

#endif

BSTArbre.hh

#ifndef BSTARBRE_HH
#define BSTARBRE_HH

#include "BSTNode.hh"
#include <iostream>
#include <exception>
using namespace std;

template <class K, class V>
class BSTArbre
{
public:
    BSTArbre() : root(nullptr), _size(0){};
    BSTArbre(const BSTArbre<K, V> &orig)
    {
        this->_size = orig._size;
        // TODO: revisar que este bien
        this->root = new BSTNode<K, V>(orig.root);
    };

    BSTArbre(const BSTNode<K, V>& r)
    {
        // TODO: revisar que este bien
        this->_size = 0;
        this->root = new BSTNode<K, V>(r);
    };

    virtual ~BSTArbre()
    {
        destroyRec(root);
    };

    void destroyRec(BSTNode<K, V> *n)
    {
        if (n != nullptr)
        {
            destroyRec(n->getLeft());
            destroyRec(n->getRight());
            delete n;
        }
    }

    bool empty() const { return root == nullptr; }
    int size() const { return _size; };
    int height() const
    {
        if (empty())
            return 0;
        return root->height();
    };

    BSTNode<K, V> *insert(const K &k, const V &value) {
        return _insert(this->root, nullptr, k, value, false); 
        // el padre de root es nullptr
    }

    BSTNode<K,V>* _insert(BSTNode<K, V> *r, BSTNode<K, V> *parent,
                    const K &k, const V &value, bool left) {
        if (r == nullptr) {
            r = new BSTNode<K, V>(k);
            r->insertValue(value);
            r->setParent(parent);
            if (!left and parent != nullptr) {
                parent->setRight(r);
            }
            else if (left and parent != nullptr) parent->setLeft(r);
            return r;
        }
        else {
            if (k > r->getKey()) {
                return _insert(r->getRight(), r, k, value, false);
            }
            else return _insert(r->getLeft(), r, k, value, true);
        }
    }

        

    const list<V> &valuesOf(const K &k) const
    {
        BSTNode<K, V> *n = search(k);
        if (n == nullptr)
            throw invalid_argument("Key not found!");
        else
            return n->getValues();
    }

    void printValues(const list<V> &values) const
    {

        for (auto it = values.begin(); it != values.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }

    void printPreorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printPreorder(n->getLeft());
            printPreorder(n->getRight());
        }
    }

    void printInorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            printInorder(n->getLeft());
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printInorder(n->getRight());
        }
    }
    void printPostorder(const BSTNode<K, V> *n = nullptr) const
    {

        if (n != nullptr)
        {
            printPostorder(n->getLeft());
            printPostorder(n->getRight());
            cout << n->getKey() << endl;
            printValues(n->getValues());
        }
    }

    BSTNode<K, V>* getRoot() {
        return this->root;
    }


    const list<BSTNode<K, V> *> &getLeafNodes() const;

    void printSecondLargestKey() const {
        if (empty())
            throw invalid_argument("Empty tree!");
        else
            printSecondLargestKey(root);
    };

    void printSecondLargestKey(BSTNode<K, V>* root) {
        if (root->getRight() == nullptr) {
            cout << root->getKey() << endl;
        }
        else {
            printSecondLargestKey(root->getRight());
        }
    }

    void mirrorTree() {
        if (empty())
            throw invalid_argument("Empty tree!");
        else
            mirrorTree(root);
    };

    void mirrorTree(BSTNode<K, V>* root) {
        if (root->getLeft() != nullptr) {
            mirrorTree(root->getLeft());
        }
        if (root->getRight() != nullptr) {
            mirrorTree(root->getRight());
        }
        BSTNode<K, V>* temp = root->getLeft();
        root->setLeft(root->getRight());
        root->setRight(temp);
    }

protected:
    BSTNode<K, V> *root;
    BSTNode<K, V> *search(const K &k) const
    {
        BSTNode<K, V> *act = root;
        while (act != nullptr)
        {
            if (act->getKey() < k)
            {
                act = act->getLeft();
            }
            else if (act->getKey() > k)
            {
                act = act->getRight();
            }
            else
                return act;
        }
        return nullptr;
    }

private:
    int _size;
    /* Mètodes auxiliars definiu aquí els que necessiteu */
};

#endif

G. Sliepen · Accepted Answer · 2022-05-20 21:59:12Z

Stick with a single language

I see you have some Catalan comments, and instead of BSTTree you write BSTArbre, but all other types, variables and member functions are named in English. I recommend you be consistent and write everything in English then; it's already required for someone to understand most of your code, and this way people who don't read Catalan can read your code without issues.

Don't make the destructors `virtual`

I see you made the destructors virtual. That is only necessary if you are writing a base class, however it doesn't look like your classes are meant to be inherited from, so remove the virtual keyword. Or in the case of BSTNode, remove the destructor entirely, since it's empty anyway.

You could make `BSTNode` part of `BSTArbre`

You can nest classes in C++. This allows you to write:

class BSTArbre {
    public:
    class Node {
        ...
    };
    ...
    BSTArbre(const BSTArbre &orig)
    {
        _size = orig._size;
        root = new Node(orig.root);
    };
    ...
protected:
    Node *root;
    ...
};

Note how you no longer need to append <K, V> to the node type, as the inner class is part of the template as well. Note that you can also write BSTArbre without <K, V> inside the template, you don't have to repeat the template parameters for types that are within the template.

Unnecessary use of `this->`

It is almost never necessary to use this-> in C++. I would remove it everywhere. The exceptions might be functions like setParent(), but you could avoid it even there by renaming the function parameter in some way.

Prefer `'\n'` over `std::endl`

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually not necessary and might impact performance.

Make helper function `private`

There are several helper functions, like destroyRec() and _insert() that should only be called by other member functions of BSTArbre. Make them private, so they cannot be accidentily called. Keep the public API tidy. If you don't, you risk other code starting to call the helper functions, and that means it will be much harder to change your class later without breaking users.

Handle corner cases where possible

Why throw an exception when trying to mirror an empty tree? It seems natural that the result of mirroring an empty tree is just another empty tree, so I would return without any error instead.

`size()` always returns zero

You are never updating _size, so size() will always return zero. Either make sure you properly update _size whenever nodes get added or removed, or remove the member variable _size and let size() calculate it every time it is called.

Consider adding iterators

Your class has functions to print the contents to std::cout in pre/in/post-order. But what if I want to print to a file? What if I want to do something else with the values I've stored in the tree? Instead of adding more and more member functions, it would be much nicer if BSTArbre would just provide the means to iterate over the elements in the desired order, and let the caller decide what to do with it. Imagine being able to write:

for (auto& node: tree.preorder()) {
    std::cout << node->getKey() << '\n';
}

This will require some work; you would have to create a preorder() functions that returns a class that has begin() and end() member functions, those member functions should return iterators that iterate over the tree in the desired order.

I would start with just adding iterators to BSTArbre directly, such that you can write:

for (auto& node: tree) {
    ...
}

And just have that do an in-order iteration over the nodes. Find some tutorial about writing your own iterators.

This might seem a lot of work, but if you do this, then apart from range-for working with your class, many STL algorithms might also be able to work directly with your class.

Only store a single value in a node

Each BSTNode has a single key and a std::list of values. Maybe that's what you needed, but now you've had to add functions to manipulate that list, adding complexity to your classes. Instead, I would just store a single value:

V value;

And if you want to have a binary search tree that stores a list of values, you can simply have the caller make that explicit. For example, like so:

BSTArbre<int, std::list<int>> tree;

Toby Speight · Accepted Answer · 2025-11-18 12:31:59Z

`printValues`

Let's consider a function with opportunity for improvement.

    void printValues(const list<V> &values) const
    {

        for (auto it = values.begin(); it != values.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }

Let's use a range-based for loop rather than manually writing out the iterators.

    void printValues(const list<V> &values) const
    {
        for (const auto &x : values)
        {
            cout << x << " ";
        }
        cout << endl;
    }

Comparing to `nullptr`

In several places you check whether a pointer is equal to or not equal to nullptr.

Yours	Equivalent
`n == nullptr`	`!n`
`n != nullptr`	`n`

Calculating height

You write code to recursively calculate the height of trees and the depth of a given node.

    int height() const
    {
        if (isExternal())
            return 1;
        else
            return 1 + max(left->height(), right->height());
    }

This has to touch every node in a tree, which betrays the efficiency premise of a binary search tree that operations are O(log n) rather than O(n).
Instead, store this as information tagged on each node.

If we do this, then we can write a free function which finds the height of a tree.

template <class K, class V>
int height(const BSTNode<K, V>. *n) {
    if (!n) return 0;

    return n->height;
}

Balance

You implement the tools to find height, which could easily be used to determine if the tree is balanced, but you never implement any rotation or balancing operations to ensure the tree is balanced and thus, efficient. This is a distinct opportunity for improvement.

Memory management

Both BSTNode and BSTArbre contain raw pointers, but neither follows the rule of 3/5/0. This is an area for improvement.

I actually think explicit use of nullptr is the better idea here. — Reinderien
– Reinderien, Commented Nov 18 at 13:11

Stack Exchange Network

Binary Search Tree implementation in C++ with templates

2 Answers 2

Stick with a single language

Don't make the destructors `virtual`

You could make `BSTNode` part of `BSTArbre`

Unnecessary use of `this->`

Prefer `'\n'` over `std::endl`

Make helper function `private`

Handle corner cases where possible

`size()` always returns zero

Consider adding iterators

Only store a single value in a node

`printValues`

Comparing to `nullptr`

Calculating height

Balance

Memory management

You must log in to answer this question.

Hot Network Questions

Binary Search Tree implementation in C++ with templates

2 Answers 2

Stick with a single language

Don't make the destructors virtual

You could make BSTNode part of BSTArbre

Unnecessary use of this->

Prefer '\n' over std::endl

Make helper function private

Handle corner cases where possible

size() always returns zero

Consider adding iterators

Only store a single value in a node

printValues

Comparing to nullptr

Calculating height

Balance

Memory management

You must log in to answer this question.

Related

Hot Network Questions

Don't make the destructors `virtual`

You could make `BSTNode` part of `BSTArbre`

Unnecessary use of `this->`

Prefer `'\n'` over `std::endl`

Make helper function `private`

`size()` always returns zero

`printValues`

Comparing to `nullptr`