# Binary Search Tree - C++

I'm implementing several data structures in an attempt to learn C++. Below is a binary search tree that I've implemented to learn about pointers, dangling pointers, and memory leaks. I was hoping someone could critique my code, point out any problems that they may find, or any inconsistencies. Please, be as harsh you feel necessary.

Note: As far as I know this implementation works well. Although, I feel as if the remove function could be simplified some how.

BinarySearchTree.h

//
//  BinarySearchTree.h
//  Data Structures

#ifndef __Data_Structures__BinarySearchTree__
#define __Data_Structures__BinarySearchTree__

#include <stdio.h>
#include <functional>

#pragma mark - Enumerations

typedef enum : int
{
TraversalTypeInOrder,
TraversalTypePreOrder,
TraversalTypePostOrder

} TraversalType;

#pragma mark -

#pragma mark - Class Definition

template<class T>
class BinarySearchTree
{

#pragma mark - Structures

template<typename Key>
struct Node
{
Key key;

Node<Key> * left = nullptr;
Node<Key> * right = nullptr;
Node<Key> * parent = nullptr;
};

#pragma mark -

#pragma mark - Private Member Variables

Node<T> * root = nullptr;

#pragma mark -

#pragma mark - Private Helper Functions

T minimum(Node<T> * node)
{
if (node->left == nullptr)
return node->key;

return minimum(node->left);
}

T maximum(Node<T> * node)
{
if (node->right == nullptr)
return node->key;

return maximum(node->right);
}

#pragma mark -

#pragma mark - Private Action Functions

void insert(const T &key, Node<T> * node)
{
if (key < node->key)
{
if (node->left)
{
insert(key, node->left);
}
else {
Node<T> * left = new Node<T>();
left->key = key;
left->parent = node;

node->left = left;
}
}
else {
if (node->right)
{
insert(key, node->right);
}
else {
Node<T> * right = new Node<T>();
right->key = key;
right->parent = node;

node->right = right;
}
}
}

Node<T> * search(const T &key, Node<T> * node)
{
if (node == nullptr)
return nullptr;

if (key == node->key)
{
return node;
}
else if (key < node->key)
{
return search(key, node->left);
}
else {
return search(key, node->right);
}
}

void traverse(TraversalType traversalType, std::function<void(T key)> printFunctor, Node<T> * node)
{
if (node == nullptr)
return;

if (traversalType == TraversalTypePreOrder)
printFunctor(node->key);

traverse(traversalType, printFunctor, node->left);

if (traversalType == TraversalTypeInOrder)
printFunctor(node->key);

traverse(traversalType, printFunctor, node->right);

if (traversalType == TraversalTypePostOrder)
printFunctor(node->key);
}

#pragma mark -

public:

#pragma mark - Life Cycle Methods

~BinarySearchTree()
{
removeAll();
}

#pragma mark -

#pragma mark - Public Helper Functions

T minimum()
{
return minimum(root);
}

T maximum()
{
return maximum(root);
}

#pragma mark -

#pragma mark - Public Actions Functions

void insert(const T &key)
{
if (root == nullptr)
{
root = new Node<T>();
root->key = key;
}
else {
insert(key, root);
}
}

void remove(const T &key)
{
Node<T> * node = search(key);

if (node == nullptr)
return;

if (node->left != nullptr && node->right != nullptr)
{
T successorKey = minimum(node->right);
remove(successorKey);

node->key = successorKey;
}
else if (node->left == nullptr && node->right == nullptr)
{
if (node == root)
{
root = nullptr;
}
else {
if (node == node->parent->left)
node->parent->left = nullptr;
else
node->parent->right = nullptr;
}

delete node;
}
else {
if (node == root)
{
if (node->left != nullptr)
root = node->left;
else
root = node->right;
}
else {
T successorKey;

if (node->left != nullptr)
{
successorKey = maximum(node->left);
remove(successorKey);

node->key = successorKey;
}
else {
successorKey = minimum(node->right);
remove(successorKey);

node->key = successorKey;
}
}
}
}

Node<T> * search(const T &key)
{
return search(key, root);
}

void traverse(TraversalType traversalType, std::function<void(T key)> printFunctor)
{
traverse(traversalType, printFunctor, root);
}

void removeAll()
{
if (root == nullptr)
return;

remove(root->key);
removeAll();
}

#pragma mark -

};

#pragma mark -

#endif /* defined(__Data_Structures__BinarySearchTree__) */


main.cpp

//
//  main.cpp
//  Data Structures

#include <iostream>
#include <cstdlib>

#include "BinarySearchTree.h"

int main(int argc, const char * argv[])
{
srand((unsigned)time(NULL));

BinarySearchTree<int> binarySearchTree;

binarySearchTree.insert(11);
binarySearchTree.insert(9);
binarySearchTree.insert(8);
binarySearchTree.insert(10);
binarySearchTree.insert(14);
binarySearchTree.insert(13);
binarySearchTree.insert(15);

auto printNode = [](int key) -> void { printf("%d ", key); };

binarySearchTree.traverse(TraversalTypePreOrder, printNode);
printf("\n");
binarySearchTree.remove(10);
printf("\n");
binarySearchTree.traverse(TraversalTypePreOrder, printNode);

return 0;
}

• A tiny remark: you normally don't typedef enum or typedef struct in C++. That's done on C code to avoid having to qualify each usage with enum/struct. In C++, the name you give to the enum or struct is already a first class name, so the extra typedefin is unnecessary. – glampert Jul 16 '15 at 2:39

You can avoid a lot of ownership problems by using:

std::unique_ptr<Node<T>> root;


and also simplify a lot of logic into loops by using:

enum { LEFT, RIGHT };
std::unique_ptr<Node<T>> children[2];


(but still Node<T> *parent; being because it's backwards, not owning)

You should only use operator < (sometimes with arguments swapped or with the result negated), never operator ==: they might not be related.

__Data_Structures__BinarySearchTree__ is not a legal identifer for users, it is reserved for the implementation since it has two underscores in a row and/or an initial underscore followed by a capital letter. I avoid this by using #pragma once since it is supported by all compilers.

#include <cstdio> instead of #include <stdio.h>

srand seeds a poor random number generator, and time is a very predictable seed. But you don't actually call rand in this code.

I have never had cause to use anything but in-order traversals, and those are implemented by iterators.

All of your #pragma mark is really distracting. Most tools are sensible enough to use comments for documentation grouping, but most of the time that is only needed on a very coarse basis at namespace scope.

In your many of your functions, you are wasting stack with recursion unless the compiler performs TCE.

You are missing copy/move constructor/assignment operators.

This is not a self-balancing binary tree, so it will degenerate to a linked list on certain common inputs.

• Good review, but since the person asking has said they're learning C++, you might improve this review by spelling out TCE (and pointing out the places where an optimizing compiler might use it) and showing an example of move semantics. – Edward Jul 16 '15 at 11:06
• Thank you for the "pointers", ha. They are really helpful. This definitely gives me a few things to read about. Although, as Edward pointed out, would you mind spelling out TCE? I'm having a hard time finding out what it means without knowing what it stands for. – Jonathan Jul 16 '15 at 15:14
• It stands for Tail Call Elimination (sometimes also called tail call optimization) stackoverflow.com/questions/310974/… It's something the compiler does, not the programmer, but certain constructs are more amenable to such optimization. – Edward Jul 16 '15 at 15:30
• Note: #pragma once, though not part of the standard, is supported by all compilers that implement any reasonable subset of the standard. – o11c Jul 16 '15 at 17:13
• Hmm -- "all compilers" is an awfully large statement. It seems to me that advocating the use of non-standard extensions is counter to the goal of promoting portable programs, especially since there is a perfectly usable standard means of accomplishing the same thing. – Edward Jul 16 '15 at 20:17

Prefer the C++ headers for C functions when you write C++ code.

I.e:

#include <cstdio>


# Weird use of typedef

I'm not really a fan of how you use typedef here, the type int is the default backing type and it doesn't really matter which type you have in your case. As you're using C++11 you might as well use enum class.

Your enum definition should just be:

enum class TraversalType
{
InOrder,
PreOrder,
PostOrder
};


A classic case of KISS.

# Use an object oriented design

You currently use Node as a plain data structure. But if you delegate some of the work to the node class, you'll see that your code will simplify. For example search is a good candidate. While we're at it, your code requires that you have both operator < and operator == for the key type. You can rewrite your search logic like this to avoid this requirement:

Node* search(const T &a_key)
{
if (a_key < key) {
return left ? left->search(a_key) : nullptr;
}
else if (key < a_key){
return right? right->search(a_key) : nullptr;
}
else{
return node;
}
}


as long as operator < defines a partial ordering.

An added benefit of the above implementation is that instead of nullptr you can return left or right, you can use then use this to implement your insert function. How is left as an exercise for the reader.

Any method where you find yourself using node-> frequently is a good candidate to move into the Node class.

• I didn't even know about cstdio. My IDE (Xcode) automatically put <stdio.h>. With the enum, yes, after reading the question and answers to the link you provided I definitely need to be using enum class. The plain enum I was using was not type safe and enum class is type safe, which I was not aware of. Since I have to qualify? the enum members with TraversalType I assume there's no need to include it in the member names. Unless it's best practice? Wow, really good point about the object oriented design! I'm always looking to improve on this. It never dawned on me to add a search function to the – Jonathan Jul 16 '15 at 15:57
• node so it could search its children, which makes total sense. Thank you! – Jonathan Jul 16 '15 at 16:02
• @Jonathan I would not include the name of the enum type in the member's names. It breaks DRY. – Emily L. Jul 16 '15 at 16:33

There is no need to use a nested class template for Node. Node should use the same template parameters as BinarySearchTree. After all, you will not need to have a tree of Node<int> in a BinarySearchTree<float>.

You can just use:

struct Node
{
T key;

Node* left = nullptr;
Node* right = nullptr;
Node* parent = nullptr;
};


The functions minimum and maximum don't take into account the possibility that the tree is empty.

T minimum(Node* node)
{
// If node is nullptr, all three lines are problematic.
if (node->left == nullptr)
return node->key;

return minimum(node->left);
}

T maximum(Node* node)
{
// If node is nullptr, all three lines are problematic.
if (node->right == nullptr)
return node->key;

return maximum(node->right);
}


Since these functions are recursive, the check for whether the tree is empty should not be added here. Instead, they should be added in the public functions of the same name.

T minimum()
{
if ( root == nullptr )
{
// Throw some kind of exception.
}
return minimum(root);
}

T maximum()
{
if ( root == nullptr )
{
// Throw some kind of exception.
}
return maximum(root);
}

• Good point about the Node<T>. The node structure was public at one point and when I made it private I just changed the template parameter instead of removing it altogether. And great catch on the minimum and maximum. I didn't even notice that. – Jonathan Jul 16 '15 at 15:23
• min/max don't need to be checked. You can document that they don't work for empty trees (as long as you provide a way to test for empty tree). Optionally provide the less efficient checking version (look at std::vector as an example. operator[] is not checked. but at() is checked they do the same thing). – Martin York Jul 16 '15 at 15:41

## Remove

I find it interesting that you have a special case for removing the root where if it has one child, you reroot the tree on the child. That is actually a good move because it always reduces the tree height by one, whereas moving a successor up to the root doesn't necessarily reduce the tree height.

But then right after that code, you don't choose to do the same trick for an interior node. If an interior node to be removed has only one child, then you should do the same thing and move its child up one level replace the node being removed. Not only does it reduce the subtree height, it's also faster than searching for a successor.

## RemoveAll

Although the function is short and simple, I have two problems with it.

1. Right now the removal takes $O(n\log n)$ time due to finding successors to replace the root. It would be faster to remove leaf nodes instead of the root node. For example you could remove in a postorder traversal fashion, which would take only $O(n)$ time.
2. The recursion depth of this function is $O(n)$, which means it could overflow your stack. Now a good compiler will perform a tail recursion optimization and make this problem go away. But it's still something you should keep in mind when you write any recursive function.

## Recursion

As mentioned above, your removeAll() function uses a tail end recursive call. Usually these kinds of recursions are very easy to rewrite in a non-recursive way (the same way a compiler would optimize it). In your case:

void removeAll()
{
if (root == nullptr)
return;

remove(root->key);
removeAll();
}


can be transformed into:

void removeAll()
{
while (1) {
if (root == nullptr)
return;

remove(root->key);
}
}


which simplifies to:

void removeAll()
{
while (root != nullptr)
remove(root->key);
}


But again, remember that I recommend completely rewriting the removeAll() function to delete in a postorder traversal like this:

void removeAll(Node *node)
{
if (node == nullptr)
return;

removeAll(node->left);
removeAll(node->right);
delete node;
}

void removeAll()
{
removeAll(root);
root = nullptr;
}


I feel like even the above can be made non-recursive, because you have a parent pointer. Here's how you could free the whole tree in a non-recursive function (not tested):

void removeAll()
{
Node *next;

for (Node *p = root; p != nullptr; p = next) {
if (p->left != nullptr) {
next = p->left;
p->left = nullptr;
} else if (p->right != nullptr) {
next = p->right;
p->right = nullptr;
} else {
next = p->parent;
delete p;
}
}
}

• Awesome! Thank you for pointing out the problem with the remove function. I didn't think about doing that for interior nodes as well. For the removeAll, Wow, I've never heard of tail recursion (I'm still in school) but that's really, really cool. Thank you very much for point that out. Do you recommend using tail recursion whenever possible? – Jonathan Jul 16 '15 at 15:38
• @Jonathan Actually I try to avoid recursion when I can. But when you need to use it, make sure you know that your maximum recursion depth will be reasonable (such as $O(\log n)$ instead of $O(n)$). Tail recursion is slightly better than "normal recursion" because compilers these days will rewrite the tail end to just jump back to the beginning of the function without using extra stack space. – JS1 Jul 16 '15 at 18:01