Data Structures and Algorithms (DSA)  

DSA Binary Search Tree (BST)

Introduction

In Data Structures and Algorithms (DSA), the Binary Search Tree (BST) is one of the most important and widely used data structures. A BST helps in searching, inserting, and deleting elements efficiently. It is commonly asked in coding interviews, competitive programming, and forms the foundation for advanced data structures like AVL Trees and Red-Black Trees.

What is a Binary Search Tree?

A Binary Search Tree (BST) is a special type of binary tree where:

  1. Each node has at most two children: the left child and the right child.

  2. The value of the left child is always less than the parent node.

  3. The value of the right child is always greater than the parent node.

  4. This property holds recursively for all nodes in the tree.

Example Structure

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

πŸ‘‰ In this BST

  • Left subtree of 50 contains values smaller than 50.

  • Right subtree of 50 contains values greater than 50.

Why Use a Binary Search Tree?

  • βœ… Efficient Searching – Average time complexity is O(log n).

  • βœ… Sorted Structure – Inorder traversal of a BST gives sorted elements.

  • βœ… Dynamic Data Handling – Supports insert and delete operations efficiently.

  • βœ… Foundation for Advanced Trees – Basis for balanced trees like AVL and Red-Black Trees.

Basic Operations on Binary Search Tree

1. Insert into BST

To insert an element:

  1. Start at the root.

  2. If the new value is smaller β†’ move to the left child.

  3. If the new value is larger β†’ move to the right child.

  4. Repeat until you find a null spot.

class Node {
    int value;
    Node left, right;

    Node(int value) {
        this.value = value;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int value) {
        root = insertRec(root, value);
    }

    Node insertRec(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }
        if (value < root.value)
            root.left = insertRec(root.left, value);
        else if (value > root.value)
            root.right = insertRec(root.right, value);
        return root;
    }
}

2. Search in BST

To search for an element:

  • If the element matches the root β†’ found.

  • If smaller β†’ search in the left subtree.

  • If larger β†’ search in the right subtree.

boolean search(Node root, int key) {
    if (root == null) return false;
    if (root.value == key) return true;
    return key < root.value
        ? search(root.left, key)
        : search(root.right, key);
}

3. Delete in BST

Deleting a node has 3 cases:

  1. Leaf Node (no children): Just remove it.

  2. One Child: Replace the node with its child.

  3. Two Children: Replace with inorder successor (smallest value in right subtree).

Node delete(Node root, int key) {
    if (root == null) return root;

    if (key < root.value)
        root.left = delete(root.left, key);
    else if (key > root.value)
        root.right = delete(root.right, key);
    else {
        if (root.left == null)
            return root.right;
        else if (root.right == null)
            return root.left;

        root.value = minValue(root.right);
        root.right = delete(root.right, root.value);
    }
    return root;
}

int minValue(Node root) {
    int min = root.value;
    while (root.left != null) {
        min = root.left.value;
        root = root.left;
    }
    return min;
}

4. Traversals in BST

Traversals are ways to visit nodes:

  • Inorder (Left β†’ Root β†’ Right) β†’ Sorted order

  • Preorder (Root β†’ Left β†’ Right)

  • Postorder (Left β†’ Right β†’ Root)

void inorder(Node root) {
    if (root != null) {
        inorder(root.left);
        System.out.print(root.value + " ");
        inorder(root.right);
    }
}

πŸ‘‰ Example Inorder Traversal Output for the tree:

20 30 40 50 60 70 80

Time Complexity of BST Operations

OperationBest CaseAverage CaseWorst Case
SearchO(log n)O(log n)O(n)
InsertO(log n)O(log n)O(n)
DeleteO(log n)O(log n)O(n)

⚠️ Worst case happens when the tree becomes skewed (like a linked list). To avoid this, use balanced BSTs (e.g., AVL, Red-Black Tree).

🎨 Infographic: Binary Search Tree (BST) Quick Summary

πŸ“Œ Structure of a BST

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

  • Left child < Parent

  • Right child > Parent

  • Applies recursively

⚑ Operations in BST

  • Insert β†’ Place based on value comparison

  • Search β†’ Go left if smaller, right if larger

  • Delete β†’ Handle leaf, one child, or two children

πŸ”„ Traversals

  • Inorder β†’ Sorted

  • Preorder β†’ Copy

  • Postorder β†’ Delete

⏱️ Time Complexity

OperationAvg CaseWorst Case
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)

⚠️ Skewed BST behaves like a linked list.

Summary

The Binary Search Tree (BST) is a powerful data structure in DSA used for fast searching, insertion, and deletion. It maintains a sorted structure and supports different tree traversals. While it is efficient in most cases with O(log n) complexity, in the worst case it can degrade to O(n). That’s why balanced versions of BST are used in real-world applications.

Membership not found