Binary Search Tree-(BST) Operations



A Binary Search Tree (BST) is a binary tree in which each node has the following property:

  • The left subtree of a node contains only nodes with keys less than the node’s key.

  • The right subtree of a node contains only nodes with keys greater than the node’s key.

  • Both left and right subtrees must also be BSTs.


Properties of a Binary Search Tree


Binary Tree Structure:
    Each node in the tree has at most two children: a left child and a right child.
    The left subtree of a node contains only nodes with values less than the node's value.
    The right subtree of a node contains only nodes with values greater than the node's value.

Ordering Property:
    For any node n, all nodes in its left subtree have values less than n, and all nodes in its right subtree         have values greater than n.

No Duplicates:
    A binary search tree does not allow duplicate values.

Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order, starting from an empty tree.

✅ Common BST Operations

  1. Creation of BST Node

    • Allocate memory for a new node.

    • Initialize data, left, and right.

  2. Insertion

    • Compare the new key with the root.

    • If smaller, go left; if larger, go right.

    • Repeat recursively until the correct position is found.

  3. Searching

    • Start at root.

    • If key < root, search in left subtree.

    • If key > root, search in right subtree.

    • If equal, node is found.

  4. Traversal

    • Inorder (L, Root, R): Gives sorted order.

    • Preorder (Root, L, R).

    • Postorder (L, R, Root).

  5. Finding Minimum and Maximum

    • Minimum → Keep moving left until NULL.

    • Maximum → Keep moving right until NULL.

  6. Deletion

    • Case 1: Node is a leaf → Delete directly.

    • Case 2: Node has one child → Replace node with its child.

    • Case 3: Node has two children → Replace with inorder successor (or predecessor), then delete successor.


Algorithms and Pseudo code : Operations on a Binary Search Tree
Definition and Creation

Define  tree node with data(key) value and also left and right pointers

// Define node structure
struct node {
    int data;
    struct node *left, *right;
};

Allocate memory and set the data and also the left and right pointers

// Function to create a new node
struct node* createNode(int value) {
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;

Insertion

  • To insert a new value into the tree, compare it to the current node's value.
  • If the value is less than the current node, go to the left subtree; if greater, go to the right subtree.
  • Repeat this process until an empty spot is found, then insert the new value as a leaf.

Insertion in a BST is also a straightforward operation. If we need to insert an element x, we first search for x. If x is present, there is nothing to do. If x is not present, then our search procedure ends in a null link. It is at this position of this null link that x will be inserted.

Algorithm
  • If the tree is empty is null, create a new node with the given key and return it.
  • else Compare the key with the current node's key.
  • If the key is less than the current node's key, recursively insert into the left subtree.
  • If the key is greater than the current node's key, recursively insert into the right subtree.
  • return the modified node.

pseudo code:
struct Node* insert(struct Node* node, int key) {
    // Base case: if the tree is empty, create a new node
    if (node == NULL) {
        return createNode(key);
    }
    // Compare the key with the current node's key
    if (key < node->key) {
        // Recursively insert into the left subtree
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        // Recursively insert into the right subtree
        node->right = insert(node->right, key);
    }
    // Return the modified node
    return node;
}

Search

    To search for a value in the tree, compare it to the current node's value.
    If the value is equal to the current node's value, the search is successful.
    If the value is less than the current node, search in the left subtree; if greater, search in the right subtree.

    Search is straightforward in a BST. Start with the root and keep moving left or right using the BST property. If the key we are seeking is present, this search procedure will lead us to the key. If the key is not present, we end up in a null link

    Algorithm
  • If the root is null or the key is equal to the root's key, return the root (key found).
  • If the key is smaller than the root's key, recursively search in the left subtree.
  • If the key is greater than the root's key, recursively search in the right subtree.

    Pseudo code
    struct Node* search(struct Node* root, int key) {
        // Base cases: the key is not present or the root is null
        if (root == NULL || root->key == key) {
            return root;
        }

        // Key is smaller than the root's key, search in the left subtree
        if (key < root->key) {
            return search(root->left, key);
        }

        // Key is greater than the root's key, search in the right subtree
        return search(root->right, key);
    }

    Traversal

    In-order Traversal: Visit the left subtree, then the current node, and finally the right subtree. This results in a sorted list of values.
    Pre-order Traversal: Visit the current node, then the left subtree, and finally the right subtree.
    Post-order Traversal: Visit the left subtree, then the right subtree, and finally the current node.

    Note that inorder traversal of a binary search tree always gives a sorted sequence of the values. This is a direct consequence of the BST property. This provides a way of sorting a given sequence of keys: first, create a BST with these keys and then do an inorder traversal of the BST so created.
(a) Inorder Traversal
void inorder(struct node* root) 
{ if (root != NULL) { 
inorder(root->left);
 printf("%d ", root->data); 
inorder(root->right); }
}
(b) Preorder Traversal
void preorder(struct node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

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

Minimum and Maximum

  • Find the minimum value by traversing the left subtree until a leaf is reached.
  • Find the maximum value by traversing the right subtree until a leaf is reached.
Note that the highest valued element in a BST can be found by traversing from the root in the right direction all along until a node with no right link is found (we can call that the rightmost element in the BST).
The lowest valued element in a BST can be found by traversing from the root in the left direction all along until a node with no left link is found (we can call that the leftmost element in the BST).

pseudo code
int findMinimum(struct Node* root) {
    // Base case: the leftmost leaf node contains the minimum value
    while (root->left != NULL) {
        root = root->left;
    }
    return root->key;
}
int findMaximum(struct Node* root) {
    // Base case: the rightmost leaf node contains the maximum value
    while (root->right != NULL) {
        root = root->right;
    }
    return root->key;
}

Deletion

To delete a node with a specific value:
  •     If the node is a leaf or has only one child, remove the node and replace it with its child.
  •    If the node has two children, find the node's in-order successor (the smallest node in its right subtree),      replace the node's value with the successor's value, and then delete the successor.


Deletion Example:








// Delete a node
struct node* deleteNode(struct node* root, int key) {
    if (root == NULL) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        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;
        }
        struct node* temp = findMin(root->right); // you can also find inorder successor
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}


Note:Average case complexity of Search, Insert, and Delete Operations is O(log n), where n is the number of nodes in the tree.

If we repeatedly insert a sorted sequence of values to form a BST, we obtain a completely skewed BST. The height of such a tree is n - 1 if the tree has n nodes. Thus, the worst case complexity of searching or inserting an element into a BST having n nodes is O(n).

These operations ensure that a binary search tree maintains its properties, providing efficient access and manipulation of data with logarithmic time complexity for balanced trees. It's important to note that if the tree becomes unbalanced, the time complexity of operations may degrade to linear, and techniques like AVL trees or red-black trees can be used to maintain balance.


C Program Implementation BST Tree operations


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

// Define node structure
struct node {
    int data;
    struct node *left, *right;
};

// Function to create a new node
struct node* createNode(int value) {
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Insert a node into BST
struct node* insert(struct node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);
    return root;
}

// Search in BST
struct node* search(struct node* root, int key) {
    if (root == NULL || root->data == key)
        return root;
    if (key < root->data)
        return search(root->left, key);
    return search(root->right, key);
}

// Find minimum value node
struct node* findMin(struct node* root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

// Find maximum value node
struct node* findMax(struct node* root) {
    if (root == NULL) return NULL;
    while (root->right != NULL)
        root = root->right;
    return root;
}

// Delete a node
struct node* deleteNode(struct node* root, int key) {
    if (root == NULL) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        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;
        }
        struct node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

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

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

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

// Main program
int main() {
    struct node* root = NULL;
    int choice, value, key;
    struct node* result;

    while (1) {
        printf("\n\n--- Binary Search Tree Menu ---\n");
        printf("1. Insert\n");
        printf("2. Search\n");
        printf("3. Delete\n");
        printf("4. Inorder Traversal\n");
        printf("5. Preorder Traversal\n");
        printf("6. Postorder Traversal\n");
        printf("7. Find Minimum\n");
        printf("8. Find Maximum\n");
        printf("9. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                root = insert(root, value);
                printf("%d inserted.\n", value);
                break;

            case 2:
                printf("Enter value to search: ");
                scanf("%d", &key);
                result = search(root, key);
                if (result != NULL)
                    printf("%d found in the BST.\n", key);
                else
                    printf("%d not found in the BST.\n", key);
                break;

            case 3:
                printf("Enter value to delete: ");
                scanf("%d", &key);
                root = deleteNode(root, key);
                printf("%d deleted (if it existed).\n", key);
                break;

            case 4:
                printf("Inorder Traversal: ");
                inorder(root);
                printf("\n");
                break;

            case 5:
                printf("Preorder Traversal: ");
                preorder(root);
                printf("\n");
                break;

            case 6:
                printf("Postorder Traversal: ");
                postorder(root);
                printf("\n");
                break;

            case 7:
                result = findMin(root);
                if (result != NULL)
                    printf("Minimum value = %d\n", result->data);
                else
                    printf("BST is empty.\n");
                break;

            case 8:
                result = findMax(root);
                if (result != NULL)
                    printf("Maximum value = %d\n", result->data);
                else
                    printf("BST is empty.\n");
                break;

            case 9:
                printf("Exiting program.\n");
                exit(0);

            default:
                printf("Invalid choice! Please try again.\n");
        }
    }
    return 0;
}

Example: University Questions

Show the structure of the binary search tree after adding each of the following values in the order 2,5,1,7,10,9,11,6.. What is the height of the created Tree. 



Comments

Post a Comment

Popular posts from this blog

Data Structures and Algorithms PCCST303 KTU 2024 Scheme- Dr Binu V P

About Me Syllabus and Evaluation Scheme  Model Question Paper and Answers PCCST303 Data Structures and Algorithms Try the following programs in lab to understand the theory better 1.Basic Concepts of Data Structures Stacks and Queues     Data Structures and Data Abstraction     Time and Space Complexity     Asymptotic Analysis and Asymptotic Notations     Best case, Worst case and Average Case Analysis of Algorithms     Frequency Count Method of Algorithm Analysis          Array as a Data Structure     Polynomial Representation using arrays      Polynomial Addition using arrays      Sparse Addition and Transpose     Stacks     Multi Stacks      Queue using array      Circular Queue using array      Double ended Queue using array     Infix to postfix and postfix evaluation     Infix to ...
Read more

Memory Allocation - First Fit

  Memory Allocation Strategy When a program requests memory from the operating system (OS) — say for creating variables, arrays, or objects — the OS must decide where in the memory to place this data. This decision-making is known as a Memory Allocation Strategy . In dynamic memory allocation, main memory (RAM) is managed in chunks called blocks . As programs request and release memory, the memory space gets fragmented into free and occupied blocks. So, an important task for the OS is to find an appropriate free block when a program requests memory. To manage this efficiently, different allocation strategies are used. First Fit Memory Allocation Strategy Definition : In the First Fit strategy, the OS searches from the beginning of memory and allocates the first free block that is large enough to satisfy the request. It doesn't check all blocks. As soon as a large enough block is found, allocation happens. Example : Assume free memory blocks of sizes: 200KB , 500KB ,...
Read more

Performance Analysis - Time and Space Complexity

Image
  📚 Performance Analysis  Performance analysis means studying how efficient an algorithm or data structure is. Mainly, we check two things: Time Complexity — How much time (number of operations) the algorithm takes. Space Complexity — How much memory (space) the algorithm uses. ✅ Goal : To predict how the algorithm will behave as the input size grows without running the code. 📍 1. Time Complexity Measures the amount of time an algorithm takes to complete. It is expressed as a function of the input size n . We usually use Big-O notation (e.g., O(n), O(log n), O(n²)) to express it. ⏳ Why it matters? Because we want algorithms that are fast even for large inputs . Example for Time Complexity: Suppose we have a simple loop: for ( int i = 0 ; i < n; i++) { printf ( "%d " , i); } The loop runs n times . Each printf is a constant-time operation. So, Time Complexity = O(n) (linear time). Types of Common Time Complexities...
Read more