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.

• 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; };
   void addNode(int key);
   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 addNode(int key, Node* leaf);
   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]
void Tree::addNode(int key)
{
   // 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;
   addNode(key, root);
}
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
   if ( key <= leaf->Key() )
   {
      if ( leaf->Left() != NULL )
         addNode(key, leaf->Left());
      else {
         Node* n = new Node();
         n->setKey(key);
         n->setParent(leaf);
         leaf->setLeft(n);
      }
   }
   else
   {
      if ( leaf->Right() != NULL )
         addNode(key, leaf->Right());
      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();

   // Add nodes
   tree->addNode(300);
   tree->addNode(100);
   tree->addNode(200);
   tree->addNode(400);
   tree->addNode(500);

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

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

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

   // 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:-
add root node ... 300
add other node ... 100
add other node ... 200
add other node ... 400
add other node ... 500
300 100 200 400 500
Node 500 found
Node 600 not found
Min=100
Max=500
Successor to 300=500
Predecessor to 300=200
200 100 400