DS Menu

Binary Search Tree



Definition of Binary Search Tree (BST)

Definition
A Binary tree T is a Binary Search Tree (BST), if each node N of T has the following property : The value at N is greater than every value in the left subtree of N and is less than every value in the right subtree of N.

A Binary Search Tree (BST) is a special type of binary tree in which the left child of a node has a value less than the node’s value and the right child has a value greater than the node’s value. This property is called the BST property and it makes it possible to efficiently search, insert, and delete elements in the tree.

BST are used to maintain a dynamically changing dataset in sorted order, which allows for quick lookup, addition, and removal of items.

A Binary Search Tree (BST) properties

  • Binary Tree: Each node has at most two children, commonly referred to as the left child and the right child.
  • Ordered Structure: For every node N, the values of all the nodes in the left subtree of N are less than the value of N, and the values of all the nodes in the right subtree of N are greater than the value of N. This is known as the binary search property.
  • No Duplicate Nodes: Typically, BSTs do not contain duplicate values. Each node has a distinct key or value.

Operations in a Binary Search Tree

BSTs support several fundamental operations, which are efficient due to their ordered nature. Here’s an overview of the primary operations:

1. Insertion Operations of BST

Insertion in a BST involves adding a new node while maintaining the BST property: for any given node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater.

Steps for Insertion:

  1. Start at the Root: Begin at the root node.
  2. Compare and Traverse:
    • If the tree is empty, the new node becomes the root.
    • Otherwise, compare the new node's value with the current node's value.
    • If the new value is smaller, move to the left child; if larger, move to the right child.
  3. Repeat the Comparison: Continue this process recursively down the tree until you reach a leaf node (a node with no children).
  4. Insert the Node: Attach the new node as the left or right child of the leaf node, depending on its value.
Algorithm
Function Insert(root, value):
    If root is NULL:
        root = CreateNode(value)
        return root

    If value < root.value:
        If root.left is NULL:
            root.left = CreateNode(value)
        Else:
            Insert(root.left, value)
    Else If value > root.value:
        If root.right is NULL:
            root.right = CreateNode(value)
        Else:
            Insert(root.right, value)
    return root

2. Search Operations of BST

Searching in a BST is efficient due to its sorted nature. You can determine the direction to move at each step (left or right).

Steps for Searching:

  1. Start at the Root: Begin at the root node.
  2. Compare and Traverse:
    • Compare the search value with the value of the current node.
    • If they match, you've found the node.
    • If the search value is smaller, move to the left child; if larger, move to the right child.
  3. Repeat Until Found or End: Continue this process. If you reach a null pointer (end of the path), the item isn't in the tree.
Algorithm
Function Search(root, value):
    If root is NULL or root.value is value:
        return root

    If value < root.value:
        return Search(root.left, value)
    Else:
        return Search(root.right, value)

3. Deletion Operations of BST

Deletion in a BST can be a bit tricky, as it needs to ensure that the BST property is maintained after removing a node. There are three cases to consider

  • Case 1 - Leaf Node
  • Case 2 - One Child
  • Case 3 - Two Children

Steps for Deletion:

  1. Find the Node: Use the search operation to find the node to be deleted.
  2. Case 1 - Leaf Node: If the node is a leaf (no children), simply remove it.
  3. Case 2 - One Child: If the node has only one child, remove the node and replace it with its child.
  4. Case 3 - Two Children:
    • Find the node's in-order successor (the smallest node in its right subtree) or in-order predecessor (the largest node in its left subtree).
    • Replace the node's value with the in-order successor/predecessor's value.
    • Delete the in-order successor/predecessor (which will be a simpler case, as it has at most one child).
Algorithm
Function Delete(root, value):
    If root is NULL:
        return root

    If value < root.value:
        root.left = Delete(root.left, value)
    Else If value > root.value:
        root.right = Delete(root.right, value)
    Else:
        // Node with only one child or no child
        If root.left is NULL:
            temp = root.right
            Free(root)
            return temp
        Else If root.right is NULL:
            temp = root.left
            Free(root)
            return temp

        // Node with two children: Get the inorder successor
        temp = MinValueNode(root.right)

        // Copy the inorder successor's content to this node
        root.value = temp.value

        // Delete the inorder successor
        root.right = Delete(root.right, temp.value)

    return root

Function MinValueNode(node):
    current = node

    // Loop down to find the leftmost leaf
    While current.left is not NULL:
        current = current.left

    return current

4. BST Traversal Operations

Traversal operations go through the nodes of the tree in a specific order. Common traversal methods include in-order, pre-order, and post-order.

Types of Traversals:

  1. In-Order Traversal (Left, Root, Right): Visit the left subtree, the root, and then the right subtree. which produces sorted output in a BST.
  2. Pre-Order Traversal (Root, Left, Right): Visit the root, the left subtree, and then the right subtree.
  3. Post-Order Traversal (Left, Right, Root): Visit the left subtree, the right subtree, and then the root.

Each traversal serves different purposes and can be chosen based on the specific needs of the algorithm or application.

Algorithm
Function InOrderTraversal(root):
    If root is not NULL:
        InOrderTraversal(root.left)
        Print root.value
        InOrderTraversal(root.right)

W3Schools.com

C Program to implement A Binary Search Tree

Program
// Binary Search Tree operations in C

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

struct node 
{
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) 
{
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) 
{
    if (root != NULL) 
    {   // Traverse left
        inorder(root->left);
        // Traverse root
        printf("%d -> ", root->key);
        // Traverse right
        inorder(root->right);
    }
}

// preorder Traversal
void preorder(struct node *root) 
{   
    if (root != NULL) 
    {
        printf("%d -> ", root->key);
        preorder(root->left);
        preorder(root->right);
    }
}

// postorder Traversal
void postorder(struct node *root) 
{
    if (root != NULL) 
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d -> ", root->key);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) 
{   // Return a new node if the tree is empty
    if (node == NULL) 
        return newNode(key);
    // Traverse to the right place and insert the node
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) 
{
    struct node *current = node;
    // Find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) 
{   // Return if the tree is empty
    if (root == NULL) 
        return root;
    // Find the node to be deleted
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else 
    {
        // If the node is with only one child or no child
        if (root->left == NULL) 
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        } 
        else if (root->right == NULL) 
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        // If the node has two children
        struct node *temp = minValueNode(root->right);
        // Place the inorder successor in position of the node to be deleted
        root->key = temp->key;
        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Function to free memory by deallocating nodes
void freeMemory(struct node *root) 
{
    if (root == NULL)
        return;
    freeMemory(root->left);
    freeMemory(root->right);
    free(root);
}

int main() {
    int choice,value;
  struct node *root = NULL;
  do
    {
        printf("\n1. Insertion\n2. Deletion\n3. inorder\n4. preorder\n5. postorder\n6. Exit");
        printf("\nEnter your choice: ");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1: printf("Enter the value to be insert: ");
                scanf("%d",&value);
                root = insert(root, value);
                break;
        case 2: printf("Enter the value to be deleted: ");
                scanf("%d",&value);
                root = deleteNode(root, value);
                break;
        case 3: inorder(root);
                break;
        case 4: preorder(root);
                break;
        case 5: postorder(root);
                break;
        case 6: freeMemory(root);
                break;
        default: printf("\nWrong selection!!! Try again!!!");  
        }
    }while(choice!=6);
    return (0);
}
Next Topic :AVL Tree