DSA Tutorial

BIANRY SEARCH TREE

🌲 Binary Search Tree (BST) in DSA

A Binary Search Tree (BST) is a special kind of binary tree where each node follows the property:

Left subtree nodes < Root node < Right subtree nodes

This property makes BST very efficient for operations like searching, insertion, and deletion, with average time complexity of O(log n).

Structure of a BST Node

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

Insertion in BST

To insert a value in BST, recursively compare it with the root and go left if it's smaller, or right if it's larger.

struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

Searching in BST

Search is efficient because we eliminate half the tree at each step.

int search(struct Node* root, int key) {
    if (root == NULL || root->data == key)
        return root != NULL;

    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

Deletion in BST

Deletion involves three cases:
1. Node with no children (leaf)
2. Node with one child
3. Node with two children (replace with inorder successor)

struct Node* findMin(struct Node* node) {
    while (node->left != NULL)
        node = node->left;
    return 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 {
        // Node 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;
        }

        // Node with two children
        struct Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Traversal in BST

Inorder traversal of a BST gives elements in sorted order:

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

Applications of BST

Used in search engines to store large databases
For maintaining sorted data
Efficient in dynamic set operations: insert, delete, search
Foundation of advanced trees like AVL Tree and Red-Black Tree

🎯 Try This:
- Implement a BST.
- Write insert, search, and delete functions.
- Perform inorder traversal to print sorted values.

🌟 Enjoyed Learning with Us?

Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!

Leave a Google Review

Topics