A Binary Search Tree Example

A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree.
The programs below describes the three basic operations in a binary search tree viz. search, insert and remove

1. Searching a node

  template <typename T>
  BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
  {
    if(*node == NULL || (*node)->key == key)
    {
      return node;
    }
    else if((*node)->key > key)
    {
      return find(&(*node)->left, key);
    }
    else
    {
      return find(&(*node)->right, key);
    }
  }

2. Inserting a node

template <typename T>
  void BST<T>::insert(T key)
  {
    BSTNode<T> **node = find(&m_root, key);
    if(*node == NULL)
    {
      *node = getNewNode(key);
    }
  }

3. Removing a node
Removing a node from binary search tree is the trickiest of all the operations. There are three cases to be considered when removing a node from a binary search tree:

Case 1. If both left and right child are null, the node can simply be deleted.

Case 2. If only one of the right child or left child is null, the address of the node is set to point to the left child or the right child which ever is not null and the current node is deleted.

Case 3. The complex of the three cases, if both left and right child are present. This requires finding the successor of the current node which is to be removed.

template <typename T>
  void BST<T>::remove(BSTNode<T> **node)
  {
    BSTNode<T> *old = *node;
    if((*node)->left == NULL)
    {
      *node = (*node)->right;
      delete old;
    }
    else if((*node)->right == NULL)
    {
      *node = (*node)->left;
      delete old;
    }
    else
    {
      BSTNode<T> **successor = getSuccessor(node);
      (*node)->key = (*successor)->key;
      remove(successor);
    }
  }

Following is the complete example showing the implementation details of the search, find and remove operations in a binary search tree.

The BST Node Class

 1 #ifndef _BSTNode_H_
 2 #define _BSTNode_H_
 3 #include <iostream>
 4 
 5 //File: BSTNode.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST;
10 
11   template <typename T>
12   class BSTNode
13   {
14   public:
15     BSTNode(T key);
16     ~BSTNode();
17 
18     friend class BST<T>;
19 
20   private:
21     BSTNode<T> *left;
22     BSTNode<T> *right;
23     T key;
24   };
25 };
26 
27 #include "BSTNode.hpp"
28 #endif //_BSTNode_H_

 1 //File: BSTNode.hpp
 2 namespace algorithms
 3 {
 4   template <typename T>
 5   BSTNode<T>::BSTNode(T key) : left(0), right(0)
 6   {
 7     this->key = key;
 8   }
 9 
10   template <typename T>
11   BSTNode<T>::~BSTNode()
12   {
13   }
14 }
15 

The Binary Search Tree Class

 1 #ifndef _BinarySearchTree_H_
 2 #define _BinarySearchTree_H_
 3 #include "BSTNode.h"
 4 
 5 //File: BST.h
 6 namespace algorithms
 7 {
 8   template <typename T>
 9   class BST
10   {
11   public:
12     BST();
13     ~BST();
14 
15     //modifiers
16     void insert(T key);
17     void remove(T key);
18     void clear();
19 
20     //accessors
21     bool find(T key);
22     bool isEmpty() const;
23 
24   private:
25     void remove(BSTNode<T> **node);
26     void clear(BSTNode<T> *node);
27     BSTNode<T>** find(BSTNode<T> **node, const T key);
28     BSTNode<T>** getSuccessor(BSTNode<T> **node);
29     BSTNode<T>* getNewNode(T key);
30 
31     //instance fields
32     BSTNode<T> *m_root;
33   };
34 };
35 
36 #include "BST.hpp"
37 #endif //_BinarySearchTree_H_

  1 //File: BST.hpp
  2 namespace algorithms
  3 {
  4   template <typename T>
  5   BST<T>::BST()
  6   {
  7     m_root = 0;
  8   }
  9 
 10   template <typename T>
 11   BST<T>::~BST()
 12   {
 13     clear();
 14   }
 15 
 16   template <typename T>
 17   void BST<T>::clear()
 18   {
 19     clear(m_root);
 20   }
 21 
 22   template <typename T>
 23   void BST<T>::clear(BSTNode<T> *node)
 24   {
 25     if(node != NULL)
 26     {
 27       clear(node->left);
 28       clear(node->right);
 29       delete node;
 30     }
 31   }
 32 
 33   template <typename T>
 34   void BST<T>::insert(T key)
 35   {
 36     BSTNode<T> **node = find(&m_root, key);
 37     if(*node == NULL)
 38     {
 39       *node = getNewNode(key);
 40     }
 41   }
 42 
 43   template <typename T>
 44   void BST<T>::remove(T key)
 45   {
 46     BSTNode<T> **node = find(&m_root, key);
 47     remove(node);
 48   }
 49 
 50   template <typename T>
 51   void BST<T>::remove(BSTNode<T> **node)
 52   {
 53     BSTNode<T> *old = *node;
 54     if((*node)->left == NULL)
 55     {
 56       *node = (*node)->right;
 57       delete old;
 58     }
 59     else if((*node)->right == NULL)
 60     {
 61       *node = (*node)->left;
 62       delete old;
 63     }
 64     else
 65     {
 66       BSTNode<T> **successor = getSuccessor(node);
 67       (*node)->key = (*successor)->key;
 68       remove(successor);
 69     }
 70   }
 71 
 72   template <typename T>
 73   BSTNode<T>** BST<T>::getSuccessor(BSTNode<T> **node)
 74   {
 75     BSTNode<T> **tmp = &(*node)->left;
 76     while((*tmp)->right != NULL)
 77     {
 78       tmp = &(*tmp)->right;
 79     }
 80     return tmp;
 81   }
 82 
 83   template <typename T>
 84   bool BST<T>::find(const T key)
 85   {
 86     BSTNode<T> **pos = find(&m_root, key);
 87     return *pos != NULL;
 88   }
 89 
 90   template <typename T>
 91   bool BST<T>::isEmpty() const
 92   {
 93     return m_root == 0;
 94   }
 95 
 96   template <typename T>
 97   BSTNode<T>** BST<T>::find(BSTNode<T> **node, const T key)
 98   {
 99     if(*node == NULL || (*node)->key == key)
100     {
101       return node;
102     }
103     else if((*node)->key > key)
104     {
105       return find(&(*node)->left, key);
106     }
107     else
108     {
109       return find(&(*node)->right, key);
110     }
111   }
112 
113   template <typename T>
114   BSTNode<T>* BST<T>::getNewNode(T key)
115   {
116     BSTNode<T> *node = new BSTNode<T>(key);
117     if(node == NULL)
118     {
119       std::cerr << "ERROR: Insufficient Memory";
120       std::cerr << std::endl;
121     }
122     return node;
123   }
124 }

The Client Program for testing the BST code above

 1 #include "BST.h"
 2 #define MAX 20
 3 using namespace algorithms;
 4 
 5 //File: Main.cpp
 6 int main(int argc, char *argv[])
 7 {
 8   int nodes[MAX] = { 50, 40, 60, 70, 80, 20, 30, 10, 90, 15, 35, 65, 75, 5, 1, 100, 110, 130, 120 };
 9   BST<int> bstInt;
10   for(int i = 0; i < MAX; ++i)
11   {
12     bstInt.insert(nodes[i]);
13   }
14 
15   std::cout << (bstInt.find(130) ? "true" : "false");
16   bstInt.remove(50);
17   std::cout << (bstInt.find(50)  ? "true" : "false");
18 
19   return 0;
20 }

Output of the run
$ ./BinarySearchTree.exe
truefalse