patterncppModerateCanonical

Binary Search Tree C++ Implementation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

implementationbinarytreesearch

Problem

I've implemented a simple binary search tree for practice purposes:

```
#ifndef BST_H
#define BST_H
template
class treeNode {
public:
treeNode *left;
treeNode *right;
T key;
treeNode(T key)
: key(key)
, left(nullptr)
, right(nullptr) {
}
};

template
class BST {
public:
BST() {
root = nullptr;
nodes = 0;
}

BST(BST const& rhs)
: nodes(rhs.size()) {
// not yet implemented
}

BST& operator = (BST rhs) {
this->swap(rhs);
}

BST& operator = (BST&& rhs) {
this->swap(rhs);
}

~BST() {
clear(root);
}

void swap(BST& other) {
std::swap(root, other.root);
std::swap(nodes, other.nodes);
}

void clear(treeNode* node) {
if(node) {
if(node->left) clear(node->left);
if(node->right) clear(node->right);
delete node;
}
}

bool isEmpty() const {
return root == nullptr;
}
void inorder(treeNode*);
void traverseInorder();

void preorder(treeNode*);
void traversePreorder();

void postorder(treeNode*);
void traversePostorder();

void insert(T const& );

void remove(T const& );

treeNode* search(const T &);

treeNode minHelper(treeNode);
treeNode* min();

treeNode maxHelper(treeNode);
treeNode* max();

size_t size() const;

void sort();
treeNode inOrderSuccessor(treeNode);
bool isBST(treeNode*) const;
bool isBST() const;

private:
treeNode *root;
size_t nodes;
};

// Smaller elements go left
// larger elements go right
template
void BST::insert(T const& value) {
treeNode *newNode = new treeNode(value);
treeNode *parent = nullptr;

// is this a new tree?
if(isEmpty()) {
root = newNode;
++nodes;
return;
}
//Note: ALL insertions are as leaf nodes
treeNode* curr = root;
// Find the Node's parent
while(curr) {

Solution

Inconsistent Code Style

Choose one coding style and use it. Some tips:

PascalCasing can be used for class/type names, but especially for template parameters.

camelCasing is mostly Java-style and fits for methods and variables (especially local vars).

c_uses_underscores almost for everything except template parameters (you can see it everywhere).

Choose what you wan't, some use CMyClass and TMyTemplate (Microsoft MFC/ATL Style), but once you choose one, use it everywhere - don't mix it.

Accessibility (what is public, private or protected)

You can use struct (all public) for your test code, but if you want to become good programmer, think about what should be public, private or protected (the last is for derived classes). I would start like this:

/// Binary Search Tree (note: this is Doxygen style documentation comment)
template class bstree { // bintree, BinarySearchTree, C/TBinTree... as you choose
    struct node { // private as first things in class are private for a good reason
        node *left, *right; // you can split it to two lines and comment like following:
        T value;   ///< node value (again, Doxygen will generate documentation from this)
    }; // no need for a constructor, it is our private struct (or protected if you like)
    node *root;    ///< root node (I prefer data first in class to see what we use)
    size_t count;  ///< nodes is not a good name, count, size, number...
public: // now is the time to show what we can do

Now I will clear it of those comments:

/// Binary Search Tree
template class bstree {
    struct node {
        node *left;   ///< left node (if any)
        node *right;  ///< right node (if any)
        T value;      ///< stored value
    };
    node *root;       ///< root node
    size_t count;     ///< total number of nodes in the tree
public:
    bstree(): root(nullptr), count(0) {}

Doxygen will be able to generate nice documentation for you if you get used to those /// comments before and

///swapping makes no sense (edit: now I see the intent - leave the destruction on the swallowed rvalue). But beware not to call

rhs.clear()

 because that could dispose the nodes:

/// move assignment
    bstree& operator = (bstree&& rhs) {
        if(&rhs == this)    // we better check
            return *this;   // not to dispose our nodes
        clear();            // dispose ours first
        root = rhs.root;    // 'steal' the nodes
        count = rhs.count;  // get the count
        rhs.root = nullptr; // clear the other
        rhs.count = 0;      // and count it
        return *this;       // this comes last
    }


Errors

remove: uninitialized parent

 - what about removing the last node?

...I am finished, unless you rewrite it and comment, what is what, what and how it should do it ;)

Have a nice day :) I hope I was not too harsh :)

Addendum

All those nice upvotes encouraged me, to rethink the design a bit.

Here is my (incomplete) code on IdeOne.com using std::unique_ptr

.

Constructors, copy and move

/// Default constructor for empty tree
    bstree(): root(), count(0) {}
//note: no need for a destructor, we use managed pointers
//  ~bstree() {}
/// Copy constructor
    bstree(const bstree& src)
    : root(src.root->copy()), count(src.count) {}
/// Move constructor
    bstree(bstree&& rhs)
    : root(std::move(rhs.root)), count(rhs.count) {
        rhs.count = 0; }
/// Move assignment
    bstree& operator = (bstree&& rhs) {
        root.swap(rhs.root);
        std::swap(count, rhs.count);
        return *this; }
/// Copy assignment
    bstree& operator = (const bstree& rhs) {
        if (this != &rhs) {// no self-copy
            root.reset(rhs.root->copy());
            count = rhs.count; }
        return *this; }


Few methods

bool contains(const T& value) {
    return root && root->find(value); }
bool insert(const T& value) {
    ptr* where = &root;
    if(root) {
        where = root->where(value);
        if(!where) return false; }
    where->reset(new node(value));
    ++count; return true;
}


Core

``
/// Binary Search Tree
template class bstree {
// I will make use of protected, feel free to use private only
// ... can be used to create another template
// ... or for debug purposes - printouts in such derived class
// ... but remember to never inherit publicly
// ... because it has public non-virtual destructor
//================================================================== node
protected:
struct node; // forward declaration
typedef std::unique_ptr
ptr; ///copy(),
right->copy());
}
//-------------------------------------------------- node: find value
/// Find node with specified value. May be called on null as well.
node* find(const T& what) {
node* it = this;
while(it) {
if(what left.get();
else if(value right.get();
else break;

Code Snippets

/// Binary Search Tree (note: this is Doxygen style documentation comment)
template<class T> class bstree { // bintree, BinarySearchTree, C/TBinTree... as you choose
    struct node { // private as first things in class are private for a good reason
        node *left, *right; // you can split it to two lines and comment like following:
        T value;   ///< node value (again, Doxygen will generate documentation from this)
    }; // no need for a constructor, it is our private struct (or protected if you like)
    node *root;    ///< root node (I prefer data first in class to see what we use)
    size_t count;  ///< nodes is not a good name, count, size, number...
public: // now is the time to show what we can do

/// Binary Search Tree
template<class T> class bstree {
    struct node {
        node *left;   ///< left node (if any)
        node *right;  ///< right node (if any)
        T value;      ///< stored value
    };
    node *root;       ///< root node
    size_t count;     ///< total number of nodes in the tree
public:
    bstree(): root(nullptr), count(0) {}

bstree();              ///< default constructor
bstree(const bstree&); ///< copy constructor (preserve what is passed)
bstree(bstree&&);      ///< move constructor (may destroy/clear what is passed)
bstree& operator = (const bstree&); ///< copy assignment
bstree& operator = (bstree&&);      ///< move assignment
bstree& operator = (bstree);        ///< wrong! would make a copy first, then like bstree&&

/// move assignment
    bstree& operator = (bstree&& rhs) {
        if(&rhs == this)    // we better check
            return *this;   // not to dispose our nodes
        clear();            // dispose ours first
        root = rhs.root;    // 'steal' the nodes
        count = rhs.count;  // get the count
        rhs.root = nullptr; // clear the other
        rhs.count = 0;      // and count it
        return *this;       // this comes last
    }

/// Default constructor for empty tree
    bstree(): root(), count(0) {}
//note: no need for a destructor, we use managed pointers
//  ~bstree() {}
/// Copy constructor
    bstree(const bstree& src)
    : root(src.root->copy()), count(src.count) {}
/// Move constructor
    bstree(bstree&& rhs)
    : root(std::move(rhs.root)), count(rhs.count) {
        rhs.count = 0; }
/// Move assignment
    bstree& operator = (bstree&& rhs) {
        root.swap(rhs.root);
        std::swap(count, rhs.count);
        return *this; }
/// Copy assignment
    bstree& operator = (const bstree& rhs) {
        if (this != &rhs) {// no self-copy
            root.reset(rhs.root->copy());
            count = rhs.count; }
        return *this; }

Context

StackExchange Code Review Q#61671, answer score: 16

Revisions (0)

No revisions yet.