A binary search tree (BST) organizes data such that each node's left subtree contains only keys less than the node, and the right subtree contains only keys greater. This ordering allows efficient search, insertion, and deletion.
Node Structure and Tree Definition
Basic node template storing a key and pointers to children:
template <class K>
struct TreeNode {
K key;
TreeNode* left;
TreeNode* right;
TreeNode(const K& k) : key(k), left(nullptr), right(nullptr) {}
};
The tree class holds a root pointer and provides public methods.
Iterative Insert
Insertion traverses the tree to find the appropriate leaf position, then links the new node.
template <class K>
bool BSTree<K>::Add(const K& k) {
if (!root_) {
root_ = new TreeNode<K>(k);
return true;
}
TreeNode<K>* curr = root_;
TreeNode<K>* prev = nullptr;
while (curr) {
prev = curr;
if (k > curr->key)
curr = curr->right;
else
curr = curr->left;
}
TreeNode<K>* fresh = new TreeNode<K>(k);
if (k > prev->key)
prev->right = fresh;
else
prev->left = fresh;
return true;
}
A temporary prev tracks the parent, enabling the link between parent and child.
Inorder Traversal
An inorder walk visits nodes in ascending key order.
template <class K>
void BSTree<K>::TraverseInternal(TreeNode<K>* node) {
if (!node) return;
TraverseInternal(node->left);
std::cout << node->key << ' ';
TraverseInternal(node->right);
}
template <class K>
void BSTree<K>::PrintInOrder() {
TraverseInternal(root_);
}
A helper function is used because the root is private.
Iterative Search
Search compares the key with the current node and moves left or right.
template <class K>
bool BSTree<K>::Contains(const K& k) const {
TreeNode<K>* curr = root_;
while (curr) {
if (k < curr->key)
curr = curr->left;
else if (k > curr->key)
curr = curr->right;
else
return true;
}
return false;
}
Deletion
Deletion handles three cases:
- Node has no child – simply remove.
- Node has one child – bypass the node.
- Node has two children – replace with the inorder successor (minimum of right subtree) and then delete that successor.
template <class K>
bool BSTree<K>::Remove(const K& k) {
TreeNode<K>* curr = root_;
TreeNode<K>* parent = curr;
// locate node
while (curr) {
if (k > curr->key) {
parent = curr;
curr = curr->right;
} else if (k < curr->key) {
parent = curr;
curr = curr->left;
} else {
// removal logic
if (!curr->left) {
if (parent == curr) // removing root
root_ = curr->right;
else if (curr == parent->left)
parent->left = curr->right;
else
parent->right = curr->right;
delete curr;
} else if (!curr->right) {
if (parent == curr)
root_ = curr->left;
else if (curr == parent->left)
parent->left = curr->left;
else
parent->right = curr->left;
delete curr;
} else {
TreeNode<K>* successor = curr->right;
TreeNode<K>* succParent = curr;
while (successor->left) {
succParent = successor;
successor = successor->left;
}
std::swap(curr->key, successor->key);
if (succParent->left == successor)
succParent->left = successor->right;
else
succParent->right = successor->right;
delete successor;
}
return true;
}
}
return false;
}
The tricky part is re-linking when removing a two-child node. The successor may have a right child, which must be attached to the successor's parent.
Recursive Versions
Recursive implementations can be cleaner, especially when using reference parameters.
Recursive Search
template <class K>
bool BSTree<K>::SearchRec(const K& k, TreeNode<K>* node) const {
if (!node) return false;
if (k < node->key)
return SearchRec(k, node->left);
if (k > node->key)
return SearchRec(k, node->right);
return true;
}
Recursive Insert with Reference
Passing the node pointer by reference allows direct modification of the parent's link.
template <class K>
bool BSTree<K>::InsertRec(const K& k, TreeNode<K>*& node) {
if (!node) {
node = new TreeNode<K>(k);
return true;
}
if (k > node->key)
return InsertRec(k, node->right);
else
return InsertRec(k, node->left);
}
Recursive Deletion
A clever approach after swapping with the successor is to recursively delete from the right subtree.
template <class K>
bool BSTree<K>::DeleteRec(const K& k, TreeNode<K>*& node) {
if (!node) return false;
if (k < node->key)
return DeleteRec(k, node->left);
if (k > node->key)
return DeleteRec(k, node->right);
// found the node to delete
if (!node->left) {
TreeNode<K>* temp = node;
node = node->right;
delete temp;
} else if (!node->right) {
TreeNode<K>* temp = node;
node = node->left;
delete temp;
} else {
TreeNode<K>* succ = node->right;
while (succ->left)
succ = succ->left;
std::swap(node->key, succ->key);
DeleteRec(succ->key, node->right); // removes the successor
}
return true;
}
Destructor, Copy Constructor, Assignment
Destructor uses a post-order traversal to delete children before the parenet:
template <class K>
void BSTree<K>::Clear(TreeNode<K>* node) {
if (!node) return;
Clear(node->left);
Clear(node->right);
delete node;
}
template <class K>
BSTree<K>::~BSTree() { Clear(root_); }
Copy constructor builds a new tree using pre-order recursion:
template <class K>
TreeNode<K>* BSTree<K>::Clone(TreeNode<K>* node) {
if (!node) return nullptr;
TreeNode<K>* copyNode = new TreeNode<K>(node->key);
copyNode->left = Clone(node->left);
copyNode->right = Clone(node->right);
return copyNode;
}
template <class K>
BSTree<K>::BSTree(const BSTree& other) {
root_ = Clone(other.root_);
}
Assignment operator uses the copy-and-swap idiom:
template <class K>
BSTree<K>& BSTree<K>::operator=(BSTree other) {
std::swap(root_, other.root_);
return *this;
}
Key-Value Extension
To support dictionary-like operations, the node is extended with a value field:
template <class K, class V>
struct KVNode {
K key;
V value;
KVNode* left;
KVNode* right;
KVNode(const K& k, const V& v) : key(k), value(v), left(nullptr), right(nullptr) {}
};
All BST operations remain essentially the same, but Find returns a pointer to the node, enabling value retrieval and udpate.
Frequency Counter Example
template <class K, class V>
KVNode<K,V>* BSTree<K,V>::Lookup(const K& k) {
KVNode<K,V>* cur = root_;
while (cur) {
if (k < cur->key)
cur = cur->left;
else if (k > cur->key)
cur = cur->right;
else
return cur;
}
return nullptr;
}
void CountWords() {
std::vector<std::string> fruits = {"apple", "banana", "apple", "cherry", "banana", "apple"};
BSTree<std::string, int> counter;
for (const auto& fruit : fruits) {
auto node = counter.Lookup(fruit);
if (node)
node->value++;
else
counter.Add(fruit, 1);
}
counter.PrintInOrder();
}
This pattern is useful for counting occurrences or building simple caches.