For every node, X, in the tree, the values of all the keys in its left subtree are smaller than the key value of X, and the values of all the keys in its right subtree are larger than the key value of X.

Binary Search Tree Operations

There are many operations one can perform on a binary search tree.

1. Creating a binary search tree.
2. Inserting a node into a binary search tree.
3. Finding a node in a binary search tree.
4. Deleting a node in a binary search tree.

We will use a simple class that implements a binary tree to store integer values.

Creating a Binary Tree

We create an IntBinaryTree class.
The basic node of our binary tree has the following struct declaration.
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
}
The class IntBinaryTree declaration is -

IntBinaryTree.h

class IntBinaryTree
 {
private:
struct TreeNode
{ 
int value;
TreeNode *left;
TreeNode *right;
 };

TreeNode *root;
void destroySubTree(TreeNode *);
 void deleteNode(int, TreeNode *&);
void makeDeletion(TreeNode *&);
 void displayInOrder(TreeNode *);
 void displayPreOrder(TreeNode *);
void displayPostOrder(TreeNode *);
public:
IntBinaryTree()
// Constructor 
{ root = NULL; }
 ~IntBinaryTree()
// Destructor
 { destroySubTree(root); }
 void insertNode(int);
 bool searchNode(int);
 void remove(int);
 void showNodesInOrder(void)
 {
displayInOrder(root);
}
 void showNodesPreOrder()
 {
displayPreOrder(root);
}
 void showNodesPostOrder()
 {
displayPostOrder(root);
}
};

Note, we assume that our binary tree will store no duplicate values.

void IntBinaryTree::insertNode(int num){
 TreeNode *newNode,
// Pointer to a new node
 *nodePtr;
// Pointer to traverse the tree
  // Create a new node
 newNode = new TreeNode;
 newNode->value = num;
 newNode->left = newNode->right = NULL;
  if (!root)
// Is the tree empty?
root = newNode;
 else
 {
 nodePtr = root;
while (nodePtr != NULL)
 {
if (num < nodePtr->value)
 {
if (nodePtr->left)
nodePtr = nodePtr->left;
 else
 {
nodePtr->left = newNode;
break;
 }
}

else if (num > nodePtr->value)
 {
if (nodePtr->right)
nodePtr = nodePtr->right;
 else

{
nodePtr->right = newNode;
 break;
}
 }
 else
 {
cout << "Duplicate value found in tree.\n";
 break;
}
}
 }
}

// This program builds a binary tree with 5 nodes.
#include
#include "IntBinaryTree.h“
void main(void)
{
IntBinaryTree tree;
 cout << "Inserting nodes. ";
tree.insertNode(5);
tree.insertNode(8);
 tree.insertNode(3);
tree.insertNode(12);
 tree.insertNode(9);
 cout << "Done.\n";
}