Implement Dictionary Using Binary Search Tree

• Dictionary can be implemented using binary search tree.  A binary search tree is a binary tree such that each node stores a key of a dictionary.
• Key 'k' of a node is always greater than the keys present in its left sub tree.
• Similarly, key 'k' of a node is always lesser than the keys present in its right sub tree.

Example:
                              well
                            /       \
                          bus    xmas
                         /     \          \
                       air   aero      zebra

In the above example, keys present at the left sub-tree of the root node are lesser than the key of the root node.  And also, the keys present at the right sub-tree are greater than the key of the root node.

• To insert an element in a binary search tree, check whether the root is present or not.  If root is absent, then the new node is the root.
• If root node is present, check whether the key in new node is greater than or lesser than the key in root node.
• If key in new node is less than the key in root, then traverse the left sub-tree recursively until we reach the leaf node.  Then, insert the new node to the left(newnode < leaf)/right(newnode > leaf) of the leaf.
• If the key in new node is greater than the key in root, then traverse the right sub-tree recursively until we reach the leaf node.  Then, insert the new node to the left(newnode < leaf)/right of the leaf

InsertionInBST(T, newnode)
y<-NULL           
x <- root[T]
while x != NULL
     y<-x
     if  key[z] < key
          then x <- left[x]
          else  x <- right[x]
parent[newnode] <- y
if y == NULL
   then root[T] <- newnode
else if key[newnode] < key[y]
    then left[y] <- newnode
    else right[y] <- newnode

Insert "yell" to the below binary search tree.
                          workload
                            /       \
                          bus    xmas
                         /     \          \
                       air   aero      zebra


                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

To delete a node from binary search tree, we have three different cases.
Node X has no children
Node X has one child
Node X has two children

Case 1:
If X has no children

                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

Delete "zebra" from above binary search tree.

                          workload
                         /             \
                      bus            xmas
                      /     \        /   
                   air   aero    yell

Case 2:
If X has only one child, then delete x and point the parent of x to the child of x.

                          workload
                         /             \
                      bus            xmas
                      /     \        /   
                   air   aero    yell

Delete "xmas" from the above binary search tree.

                          workload
                         /             \
                      bus            yell
                      /     \       
                   air   aero

Case 3:
If X has two children, then find its successor 'S'.  Remove 'S' from the binary search tree.  And replace X with 'S'

                          workload
                         /             \
                      bus            xmas
                      /     \        /        \
                   air   aero    yell     zebra

Remove "workload" from the above binary search tree.  The successor for "workload"(smallest element in the right subtree of "workload") is "yell".  Remove it and replace "workload with "yell".

                              yell
                            /      \
                        bus      xmas
                       /    \          \
                    air   aero      zebra

See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree

C Program To Perform Insertion, Deletion & Traversal In Threaded BST

C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs

Example program To Implement Dictionary using Binary Search Tree(in C):

---

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  struct BSTnode {
        char word[128], meaning[256];
        struct BSTnode *left, *right;
  };

  struct BSTnode *root = NULL;

  struct BSTnode * createNode(char *word, char *meaning) {
        struct BSTnode *newnode;
        newnode = (struct BSTnode *)malloc(sizeof(struct BSTnode));
        strcpy(newnode->word, word);
        strcpy(newnode->meaning, meaning);
        newnode->left = newnode->right = NULL;
        return newnode;
  }

  void insert(char *word, char *meaning) {

        struct BSTnode *parent = NULL, *current = NULL, *newnode = NULL;

        int res = 0;

        if (!root) {

                root = createNode(word, meaning);

                return;

        }

        for (current = root; current !=NULL;

           current = (res > 0) ? current->right : current->left) {

                res = strcasecmp(word, current->word);

                if (res == 0) {

                        printf("Duplicate entry!!\n");

                        return;

                }

                parent = current;

        }

        newnode = createNode(word, meaning);

        res > 0 ? (parent->right = newnode) : (parent->left = newnode);

        return;

  }

  void deleteNode(char *str) {

        struct BSTnode *parent = NULL, *current = NULL, *temp = NULL;

        int flag = 0, res = 0;

        if (!root) {

                printf("BST is not present!!\n");

                return;

        }

        current = root;

        while (1) {

                res = strcasecmp(current->word, str);

                if (res == 0)

                        break;

                flag = res;

                parent = current;

                current = (res > 0) ? current->left : current->right;

                if (current == NULL)

                        return;

        }

        /* deleting leaf node */

        if (current->right == NULL) {

                if (current == root && current->left == NULL) {

                        free(current);

                        root = NULL;

                        return;

                } else if (current == root) {

                        root = current->left;

                        free (current);

                        return;

                }

                flag > 0 ? (parent->left = current->left) :

                                (parent->right = current->left);

        } else {

                /* delete node with single child */

                temp = current->right;

                if (!temp->left) {

                        temp->left = current->left;

                        if (current == root) {

                                root = temp;

                                free(current);

                                return;

                        }

                        flag > 0 ? (parent->left = temp) :

                                        (parent->right = temp);

                } else {

                        /* delete node with two children */

                        struct BSTnode *successor = NULL;

                        while (1) {

                                successor = temp->left;

                                if (!successor->left)

                                        break;

                                temp = successor;

                        }

                        temp->left = successor->right;

                        successor->left = current->left;

                        successor->right = current->right;

                        if (current == root) {

                                root = successor;

                                free(current);

                                return;

                        }

                        (flag > 0) ? (parent->left = successor) :

                                        (parent->right = successor);

                }

        }

        free (current);

        return;

  }

  void findElement(char *str) {

        struct BSTnode *temp = NULL;

        int flag = 0, res = 0;

        if (root == NULL) {

                printf("Binary Search Tree is out of station!!\n");

                return;

        }

        temp = root;

        while (temp) {

                if ((res = strcasecmp(temp->word, str)) == 0) {

                        printf("Word   : %s", str);

                        printf("Meaning: %s", temp->meaning);

                        flag = 1;

                        break;

                }

                temp = (res > 0) ? temp->left : temp->right;

        }

        if (!flag)

                printf("Search Element not found in Binary Search Tree\n");

        return;

  }

  void inorderTraversal(struct BSTnode *myNode) {

        if (myNode) {

                inorderTraversal(myNode->left);

                printf("Word    : %s", myNode->word);

                printf("Meaning : %s", myNode->meaning);

                printf("\n");

                inorderTraversal(myNode->right);

        }

        return;

  }

  int main() {

        int ch;

        char str[128], meaning[256];

        while (1) {

                printf("\n1. Insertion\t2. Deletion\n");

                printf("3. Searching\t4. Traversal\n");

                printf("5. Exit\nEnter ur choice:");

                scanf("%d", &ch);

                getchar();

                switch (ch) {

                        case 1:

                                printf("Word to insert:");

                                fgets(str, 100, stdin);

                                printf("Meaning:");

                                fgets(meaning, 256, stdin);

                                insert(str, meaning);

                                break;

                        case 2:

                                printf("Enter the word to delete:");

                                fgets(str, 100, stdin);

                                deleteNode(str);

                                break;

                        case 3:

                                printf("Enter the search word:");

                                fgets(str, 100, stdin);

                                findElement(str);

                                break;

                        case 4:

                                inorderTraversal(root);

                                break;

                        case 5:

                                exit(0);

                        default:

                                printf("You have entered wrong option\n");

                                break;

                }

        }

        return 0;

  }

  Output(C Program To Implement Dictionary Using Binary Search Tree):

  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:old
  Meaning:not new

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:fan
  Meaning:enthosiastic devotiee of sports

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:ant
  Meaning:insect

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:candy
  Meaning:chocolate

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:ball
  Meaning:object used in cricket

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1
  Word to insert:pig
  Meaning:animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:1   
  Word to insert:queen
  Meaning:women ruler

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : old
  Meaning : not new

  Word    : pig
  Meaning : animal

  Word    : queen
  Meaning : women ruler

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:queen

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : old
  Meaning : not new

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:old

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4
  Word    : ant
  Meaning : insect
  
  Word    : ball
  Meaning : object used in cricket

  Word    : candy
  Meaning : chocolate

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:2
  Enter the word to delete:candy

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:4

  Word    : ant
  Meaning : insect

  Word    : ball
  Meaning : object used in cricket

  Word    : fan
  Meaning : enthosiastic devotiee of sports

  Word    : pig
  Meaning : animal

  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:3
  Enter the search word:ant

  Word   : ant
  Meaning: insect
  
  1. Insertion 2. Deletion
  3. Searching 4. Traversal
  5. Exit
  Enter ur choice:5