# Binary Search Trees in C++

## What is binary search trees? How to implement in C++?

This article explains the concept of binary search trees (BST) and provides a sample implementation in C++.

• Binary Search Tree (BST) is a binary tree (has atmost 2 children).
• It is also referred as sorted/ ordered binary tree.
• BST has the following properties. (notes from wikipedia)
• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

BST Operations:-
• Searching in a BST
• Examine the root node. If tree is NULL value doesn't exist.
• If value equals the key in root search is successful and return.
• If value is less than root, search the left sub-tree.
• If value is greater than root, search the right sub-tree.
• Continue until the value is found or the sub tree is NULL.
• Time complexity. Average: O(log n), Worst: O(n) if the BST is unbalanced and resembles a linked list.

• Insertion in BST
• Insertion begin as a search.
• Compare the key with root. If not equal search the left or right sub tre
• When a leaf node is reached add the new node to left or right based on the value.
• Time complexity. Average: O(log n), Worst O(n)

• Deletion in BST
• There are three possible cases to consider:
• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

## A sample implementation of BST using C++

#include
using namespace std;

// A generic tree node class
class Node {
int key;
Node* left;
Node* right;
Node* parent;
public:
Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
void setParent(Node* aParent) { parent = aParent; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
Node* Parent() { return parent; };
};

// Binary Search Tree class
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
Node* findNode(int key, Node* parent);
void walk(Node* node);
void deleteNode(int key);
Node* min(Node* node);
Node* max(Node* node);
Node* successor(int key, Node* parent);
Node* predecessor(int key, Node* parent);
private:
void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
Tree::~Tree() {
freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}

// Add a node [O(height of tree) on average]
{
// No elements. Add the root
if ( root == NULL ) {
cout < <"add root node ... " << key << endl;
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
cout < < "add other node ... " << key << endl;
}
}

void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() )
{
if ( leaf->Left() != NULL )
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setLeft(n);
}
}
else
{
if ( leaf->Right() != NULL )
else {
Node* n = new Node();
n->setKey(key);
n->setParent(leaf);
leaf->setRight(n);
}
}
}

// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
if ( node == NULL )
return NULL;
else if ( node->Key() == key )
return node;
else if ( key <= node->Key() )
findNode(key, node->Left());
else if ( key > node->Key() )
findNode(key, node->Right());
else
return NULL;
}

// Print the tree
void Tree::walk(Node* node)
{
if ( node )
{
cout < < node->Key() < < " ";
walk(node->Left());
walk(node->Right());
}
}

// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
if ( node == NULL )
return NULL;

if ( node->Left() )
min(node->Left());
else
return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
if ( node == NULL )
return NULL;

if ( node->Right() )
max(node->Right());
else
return node;
}

// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Right());
}

// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
Node* thisKey = findNode(key, node);
if ( thisKey )
return max(thisKey->Left());
}

// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
// Find the node.
Node* thisKey = findNode(key, root);

// (1)
if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(NULL);
else
thisKey->Parent()->setLeft(NULL);

delete thisKey;
}

// (2)
if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Right());
else
thisKey->Parent()->setLeft(thisKey->Right());

delete thisKey;
}
if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
{
if ( thisKey->Key() > thisKey->Parent()->Key() )
thisKey->Parent()->setRight(thisKey->Left());
else
thisKey->Parent()->setLeft(thisKey->Left());

delete thisKey;
}

// (3)
if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
{
Node* sub = predecessor(thisKey->Key(), thisKey);
if ( sub == NULL )
sub = successor(thisKey->Key(), thisKey);

if ( sub->Parent()->Key() <= sub->Key() )
sub->Parent()->setRight(sub->Right());
else
sub->Parent()->setLeft(sub->Left());

thisKey->setKey(sub->Key());
delete sub;
}
}

// Test main program
int main() {
Tree* tree = new Tree();

// Traverse the tree
tree->walk(tree->Root());
cout << endl;

// Find nodes
if ( tree->findNode(500, tree->Root()) )
cout < < "Node 500 found" < < endl;
else

if ( tree->findNode(600, tree->Root()) )
cout < < "Node 600 found" < < endl;
else

// Min & Max
cout < < "Min=" << tree->min(tree->Root())->Key() < < endl;
cout < < "Max=" << tree->max(tree->Root())->Key() < < endl;

// Successor and Predecessor
cout < < "Successor to 300=" <<
tree->successor(300, tree->Root())->Key() < < endl;
cout < < "Predecessor to 300=" <<
tree->predecessor(300, tree->Root())->Key() < < endl;

// Delete a node
tree->deleteNode(300);

// Traverse the tree
tree->walk(tree->Root());
cout << endl;

delete tree;
return 0;
}

OUTPUT:-