Binary Search Tree

The property that makes a Binary Tree into Binary Search Tree is that for every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value in X and the values of all the keys in the right subtree are larger than or equal to key value in X.

Example of a Binary Search Tree is:

The class to implement Binary Search Tree :

// Node class

template < class Etype >
class TreeNode
{
public:
        Etype element;
        TreeNode* Left;
        TreeNode* Right;
        TreeNode( Etype e = 0, TreeNode* l = NULL, TreeNode* r = NULL) : 
        element ( e), left ( l ), right ( r ) { }
        friend int height ( TreeNode *T);
        friend void inOrderTraversal ( TreeNode *T);
        friend void preOrderTraversal ( TreeNode *T);
        friend void postOrderTraversal ( TreeNode *T);
        friend class BinarySearchTree < Etype >;
};

// Binary Search Tree Class

template<class Etype>
class BinarySearchTree
{
public: 
         BinarySearchTree ( ) : Root ( NULL ) { }
         void insert ( const Etype & x ) {  insert ( x, root ); }
         void remove ( const Etype& x ) { Remove (  x, root ); }
private:
         void insert ( const Etype& x, TreeNode<Etype>* & T );
         void remove ( const Etype& x, TreeNode<Etype>* & T);
         TreeNode *root;
};

Height:

int height ( TreeNode *T)
{
        return ( T ? 1 + Max ( height ( T-> left ), height ( T-> right ) ) : 0 ) ; 
}

Inorder Traversal:

void inOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                inOrderTraversal ( T-> left );
                cout<< T-> element;
                inOrderTraversal ( T-> right);
        }
}

Preorder Traversal:


void preOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                cout<< T-> element;
                preOrderTraversal ( T-> left );
                preOrderTraversal ( T-> right);

        }

}

Postorder Traversal:


void postOrderTraversal ( TreeNode *T)
{
       if ( T )
       {
                postOrderTraversal ( T-> left );
                postOrderTraversal ( T-> right);
                cout<< T-> element;
        }

}




Insert:

Following image shows how to insert an element in Binary Search Tree:

Following is the implementation of insert( ) function:

template < class Etype >
void BinarSearchTree< Etype > :: insert ( const Etype & x, TreeNode<Etype> * & T)
{
         if ( T = = NULL )
                 T = new TreeNode<Etype> ( x );
        else
        {
                 if ( x < T -> element )
                          insert ( x, T->left );
                 else if ( x > T-> element)
                          insert ( T-> right )
         }
}


Remove:

Following image shows how to remove an element in Binary Search Tree:

Following is the implementation of remove( ) function:

template < class Etype >
void BinarySearchTree< Etype > :: remove ( const Etype & x, TreeNode<Etype> * & T)
{
        TreeNode<Etype> *tmpCell;
   
        if ( T = = NULL )
                 cout << " Element Not Found ";
        else if ( x < T-> element )
                 remove ( x, T-> left );
        else if ( x > T-> element )
                 remove ( x, T-> right );
        else       // element found
        {
                  if ( T-> left != NULL && T -> right != NULL )
                  {
                            tmpCell = findMin ( T-> right );   // Minimum element
                            T-> element = tmpCell -> element;
                            remove ( T->element, T->right );
                  }
                 else
                 {
                          tmpCell = T;
                          if ( T-> left)
                                     T = T-> left;
                         else if ( T-> right )
                                     T = T-> right;
                         delete tmpCell;
                  }
        }
}