A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.

  1. Hierarchical data structure with a single reference to root node
  2. Each node has at most two child nodes (a left and a right child)
  3. Nodes are organized by the Binary Search property:
    • Every node is ordered by some key data field(s)
    • For every node in the tree, its key is greater than its
    left child’s key and less than its right child’s key

Some BST Terminology

  1. The Root node is the top node in the hierarchy
  2. Child node has exactly one Parent node, a Parent node has at most two child nodes, Sibling nodes share the same Parent node.
  3. Leaf node has no child nodes, an Interior node has at least one child node (ex. 18 is a leaf node)
  4. Every node in the BST is a Subtree of the BST rooted at that node

Implementing Binary Search Trees in C++

Structure:


struct Node {
  int x;
  Node *left;
  Node *right;
};

Class:


class Tree
{
Node *root ;
public:
Tree()
{ root=NULL; }

void insert(int x)
{
Node *ptr=new Node;

ptr->x=x;
ptr->left=NULL;
ptr->right=NULL;

cout << "\n-------------------------------------" << endl;
cout << "Node Address: " << ptr << endl; if(root==NULL) root=ptr; else { Node *temp=root; while(true) { if(temp->x > x)
{
if(temp->left==NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp->x << endl; temp->left=ptr;
break;
}
else
temp=temp->left;
}
else
{
if(temp->right==NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp->x << endl; temp->right=ptr;
break;
}
else
temp=temp->right;
}
}
} 

cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl; } void inOrder(Node *temp) { if (temp != NULL) { inOrder(temp->left);
cout << temp->x << " "; inOrder(temp->right);
}
}

void preOrder(Node *temp)
{
if (temp != NULL)
{
cout << temp->x << " "; preOrder(temp->left);
preOrder(temp->right);
}
}

void postOrder(Node *temp)
{
if (temp != NULL)
{
postOrder(temp->left);
postOrder(temp->right);
cout << temp->x << " ";
}
}

Node *getRoot()
{ return root; }

void display(Node *temp)
{
if (temp != NULL)
{
cout << endl;
cout << "Parent: " << temp->x << endl;
cout << " Left Child of " << temp->x << ": " ; if(temp->left == NULL)
cout << "NULL" << endl;
else
cout << temp->left->x << endl;

cout << " Right Child of " << temp->x << ": " ; if(temp->right == NULL)
cout << "NULL" << endl;
else
cout << temp->right->x << endl; display(temp->left);
display(temp->right);
}
}

bool isEmpty()
{
if(root == NULL)
return true;

return false;
}

void removeAll(int value)
{
while(true)
{
Node *temp = root, *ptemp=root;

while(temp!=NULL && temp->x!=value)
{
ptemp=temp;
if(temp->x < value) temp=temp->right;
else if(temp->x > value)
temp=temp->left;
}

if(temp==NULL)
{ cout << "All nodes cotaining " << value << " are deleted" << endl; break; } else { if(temp->left==NULL && temp->right==NULL)
{
if(temp==root)
root=NULL;
else if(ptemp->left==temp)
ptemp->left=NULL;
else if(ptemp->right==temp)
ptemp->right=NULL;
}
else if(temp->left==NULL && temp->right!=NULL)
{
if(temp==root)
root=temp->right;
else if(ptemp->left==temp)
ptemp->left=temp->right;
else if(ptemp->right==temp)
ptemp->right=temp->left;
}
else if(temp->right==NULL && temp->left!=NULL)
{
if(temp==root)
root=temp->left;
else if(ptemp->left==temp)
ptemp->left=temp->left;
else if(ptemp->right==temp)
ptemp->right=temp->right;
}
else if(temp->left!=NULL && temp->right!=NULL)
{
Node *tempHolder=temp, *ptempHolder=temp;

while(tempHolder->left!=NULL)
{
ptempHolder=tempHolder;
tempHolder=tempHolder->left;
}

temp->x=tempHolder->x;
ptempHolder->left=tempHolder->right;

temp=tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl; } } } void remove(int value) { Node *temp = root, *ptemp=root; while(temp!=NULL && temp->x!=value)
{
ptemp=temp;
if(temp->x < value) temp=temp->right;
else if(temp->x > value)
temp=temp->left;
}

if(temp==NULL)
{ cout << "Value Not Found...." << endl; } else { if(temp->left==NULL && temp->right==NULL)
{
if(temp==root)
root=NULL;
else if(ptemp->left==temp)
ptemp->left=NULL;
else if(ptemp->right==temp)
ptemp->right=NULL;
}
else if(temp->left==NULL && temp->right!=NULL)
{
if(temp==root)
root=temp->right;
else if(ptemp->left==temp)
ptemp->left=temp->right;
else if(ptemp->right==temp)
ptemp->right=temp->left;
}
else if(temp->right==NULL && temp->left!=NULL)
{
if(temp==root)
root=temp->left;
else if(ptemp->left==temp)
ptemp->left=temp->left;
else if(ptemp->right==temp)
ptemp->right=temp->right;
}
else if(temp->left!=NULL && temp->right!=NULL)
{
Node *tempHolder=temp, *ptempHolder=temp;

while(tempHolder->left!=NULL)
{
ptempHolder=tempHolder;
tempHolder=tempHolder->left;
}

temp->x=tempHolder->x;
ptempHolder->left=tempHolder->right;

temp=tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl; } } void deleteAllNodes(Node *temp) { if (temp != NULL) { deleteAllNodes(temp->left);
deleteAllNodes(temp->right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp->x << endl << endl;
delete temp;
}
}

~Tree()
{
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}
};

Main Function


int main() {
  Tree s;
  int x;
  
  do {
    system("CLS");
    cout << "BST Program" << endl;
    cout << "-------------------------------------" << endl;
    cout << "[I] Insert" << endl;
    cout << "[P] PreOrder Display" << endl;
    cout << "[S] InOrder Display" << endl;
    cout << "[L] PostOrder Display" << endl;
    cout << "[R] Remove" << endl;
    cout << "[Q] Remove All Nodes of Value Entered" << endl;
    cout << "[D] Display" << endl;
    cout << "[E] Exit" << endl;
    cout << "-------------------------------------" << endl;
    cout << ">> ";
    switch(getch()) {
      case 'i':
      case 'I':
        cout << "Enter Value: "; cin >> x;
        s.insert(x);
        cout << "Node Added Successfully." << endl;
        break;
      case 'p':
      case 'P':
        cout << "PreOrder: ";
        s.preOrder(s.getRoot());
        break;
      case 'l':
      case 'L':
        cout << "PostOrder: ";
        s.postOrder(s.getRoot());
        break;
      case 's':
      case 'S':
        cout << "InOrder: ";
        s.inOrder(s.getRoot());
        break;
      case 'd':
      case 'D':
        if(!s.isEmpty())
        s.display(s.getRoot());
        else
        cout << "404! Node Not Found..." << endl;
        break;
        break;
      case 'R':
      case 'r':
        if(!s.isEmpty()) {
          cout << "Enter Value to Delete: "; cin >> x;
          s.remove(x);
        }
        else
        cout << "404! Node Not Found..." << endl;
        break;
      case 'q':
      case 'Q':
        if(!s.isEmpty()) {
          cout << "Enter Value to Delete: "; cin >> x;
          s.removeAll(x);
        }
        else
        cout << "404! Node Not Found..." << endl;
        break;
      case 'E':
      case 'e':
        cout << "Program Exit Successfully..." << endl;
        return 0;
      default:
        cout << "400! Invalid Option.." << endl;
    }
    cout << "\nPress any key to continue....";
    getch();
  }
  while(1);
  
  return 0;
}