Since we plan to store any type in the tree we parametrize it
#pragma once
#include <iostream>
#include <algorithm>
template<typename T>
The node of the tree. Has a value and a pointer to left and right children.
struct Node {
T val;
Node* left;
Node* right;
Node(T v = T{}, Node* l = nullptr, Node* r = nullptr)
:val(v), left(l), right(r) {}
};
Interface for a basic binary search tree. We only need to keep track of the root. Unlike standard STL containers we don’t define a iterator to keep things simple. In a later versions we will include an iterator interface. Also most methods have a private and a public version. The public versions do not take a parameter because we want the root to be unaccessible to the used, instead they call the private version which has access to the root node.
template<typename T>
class bst {
private:
Node<T>* root;
void insert(Node<T>* &, T);
void postorder(const Node<T>*);
bool find(const Node<T>*, T);
int height(const Node<T>*);
int numNodes(const Node<T>*);
Node<T> * findMin(Node<T>*);
void erase(Node<T>* &, T);
public:
bst() :root(nullptr) {}
void insert(T );
void postorder();
bool find(T);
int height();
int numNodes();
T findMin();
void erase(T );
};
Implementation of the postorder traversal. Check the lecture nodes for explanation.
template<typename T>
void bst<T>::postorder(const Node<T>* t) {
if (t == nullptr)return;
postorder(t->left);
postorder(t->right);
std::cout << t->val << ",";
}
The public version of postorder traversal. It calls the private version with root as a parameter
template<typename T>
void bst<T>::postorder() {
postorder(root);
}
Inserting a value in the tree. First we have to find the proper place where to insert the value
then we create a node at that place. This is done in a recursive fashion. Check the lecture notes for more detailed explanation.
Note that we pass the pointer to the current node by reference. To understand why suppose
that the last node which is not null is called last and stores a value smaller than
the val we are trying to insert. In this case the final call would be
insert(last->right,val); where last->right is null. From the signature of insert
we have that t=last->right. So if we don’t pass it by reference a copy is made so
last->right it not changed.
template<typename T>
void bst<T>::insert(Node<T>* &t, T val) {
if (t == nullptr) t = new Node<T>(val);
else if (val > t->val)insert(t->right, val);
else insert(t->left, val);
}
Private version. This is what the user calls.
template<typename T>
void bst<T>::insert(T v) {
insert(root, v);
}
Similar reasoning to insert. If the value we are looking for is greater than the value of the current node go right, otherwise go left until we find it or not.
template<typename T>
bool bst<T>::find(const Node<T>* t, T val) {
if (t == nullptr) return false;
if (t->val == val)return true;
else if (t->val < val) return find(t->right, val);
else return find(t->left, val);
}
Public version of find.
template<typename T> bool bst<T>::find(T v) {
return find(root, v);
}
Computer the height of the tree recursively in a postorder fashion. The base case is the height of a null node which is -1. This done so that the height of a leaf is zero.
template <typename T>
int bst<T>::height(const Node<T>* t) {
if (t == nullptr) return -1;
int hl = height(t->left);
int hr = height(t->right);
return std::max(hl, hr) + 1;
}
template <typename T>
int bst<T>::height() {
return height(root);
}
Recursively count the number of nodes in a postorder fashion. The idea is the same as in computing the height.
template <typename T>
int bst<T>::numNodes(const Node<T>* t) {
if (t == nullptr) return 0;
int nl = numNodes(t->left);
int nr = numNodes(t->right);
return 1 + nl + nr;
}
template<typename T>
int bst<T>::numNodes() {
return numNodes(root);
}
By construction of the binary search tree the minimum is the leftmost node.
template<typename T>
Node<T> * bst<T>::findMin(Node<T>* t) {
if (t->left == nullptr) return t;
else return findMin(t->left);
}
template<typename T>
T bst<T>::findMin() {
return findMin(root)->val;
}
Recall from the lecture notes that when erasing a node we consider three different cases. The first case is when the node is a leaf then we just delete it. The second case is when the a node has a single child we just replace it by the child. Finally, when the node has two children we replace its value by the smallest value on the right (or the largest on the left) and we delete the smallers(largest) value.
template <typename T>
void bst<T>::erase(Node<T>* & t, T val) {
if (t == nullptr) return;
if (t->val < val)erase(t->right, val);
else if (t->val > val) erase(t->left, val);
// found the node
else if (t->left != nullptr && t->right != nullptr) {
Node<T>* min = findMin(t->right);
t->val = min->val;
erase(t->right, min->val);
}
else {
Node<T>* old = t;
t = (t->left != nullptr) ? t->left : t->right;
delete old;
}
}
template <typename T>
void bst<T>::erase(T val) {
erase(root, val);
}