Algorithm


A Binary Search Tree (BST) is a binary tree data structure with the following properties:

  1. Binary Tree Structure: Each node in a BST has at most two children, which are referred to as the left child and the right child.

  2. Value Ordering: For each node in the tree, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value. This ordering property ensures that the BST is a useful data structure for searching, insertion, and deletion operations.

Here's a simple example of a Binary Search Tree:

markdown
    5
   / \
  3   8
 / \ / \
1  4 7  9
 

In this example, for any node, the values in its left subtree are less than the node's value, and the values in its right subtree are greater than the node's value.

Operations on a Binary Search Tree:

  1. Search:

    • Start at the root node.
    • If the target value is equal to the current node's value, return the node.
    • If the target value is less than the current node's value, search in the left subtree.
    • If the target value is greater than the current node's value, search in the right subtree.
  2. Insertion:

    • Search for the value as you would in the search operation.
    • If the value is not found, insert a new node with the given value at the appropriate position according to the BST property.
  3. Deletion:

    • Search for the node to be deleted.
    • If the node has no children, simply remove it.
    • If the node has one child, replace it with its child.
    • If the node has two children, find the node's in-order successor (or predecessor), replace the node's value with the successor's (or predecessor's) value, and recursively delete the successor (or predecessor).

Time Complexity:

  • Search, Insertion, and Deletion: O(log n) on average, where n is the number of nodes in the tree.
  • In the worst case (unbalanced tree), these operations can degrade to O(n), but maintaining balance (e.g., using a self-balancing BST like AVL tree or Red-Black tree) helps avoid this scenario.

Binary Search Trees are commonly used in computer science due to their efficient search and insertion operations, making them suitable for a variety of applications, including databases and symbol tables.

 

Code Examples

#1 Binary Search Tree(BST) implement in Python

Code - Python Programming

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, root, key):
        if root is None:
            return TreeNode(key)

        if key < root.key:
            root.left = self._insert(root.left, key)
        elif key > root.key:
            root.right = self._insert(root.right, key)

        return root

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, root, key):
        if root is None or root.key == key:
            return root

        if key < root.key:
            return self._search(root.left, key)
        else:
            return self._search(root.right, key)

    def inorder_traversal(self):
        result = []
        self._inorder_traversal(self.root, result)
        return result

    def _inorder_traversal(self, root, result):
        if root:
            self._inorder_traversal(root.left, result)
            result.append(root.key)
            self._inorder_traversal(root.right, result)

# Example usage:
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("Inorder Traversal:", bst.inorder_traversal())

search_key = 40
search_result = bst.search(search_key)
if search_result:
    print(f"Key {search_key} found in the BST.")
else:
    print(f"Key {search_key} not found in the BST.")
Copy The Code & Try With Live Editor

#2 Binary Search Tree(BST) implement in Java

Code - Java Programming

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

public class BinarySearchTree {
    private Node root;

    public BinarySearchTree() {
        root = null;
    }

    // Insert a key into the BST
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        if (key  <  root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        }

        return root;
    }

    // Delete a key from the BST
    public void delete(int key) {
        root = deleteRec(root, key);
    }

    private Node deleteRec(Node root, int key) {
        if (root == null) {
            return root;
        }

        if (key  <  root.key) {
            root.left = deleteRec(root.left, key);
        } else if (key > root.key) {
            root.right = deleteRec(root.right, key);
        } else {
            // Node with only one child or no child
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            // Node with two children: Get the inorder successor (smallest in the right subtree)
            root.key = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

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

    // In-order traversal
    public void inOrderTraversal() {
        inOrderTraversalRec(root);
    }

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

    // Pre-order traversal
    public void preOrderTraversal() {
        preOrderTraversalRec(root);
    }

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

    // Post-order traversal
    public void postOrderTraversal() {
        postOrderTraversalRec(root);
    }

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

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // Insert keys
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // Print in-order traversal
        System.out.println("In-order traversal:");
        bst.inOrderTraversal();
        System.out.println();

        // Print pre-order traversal
        System.out.println("Pre-order traversal:");
        bst.preOrderTraversal();
        System.out.println();

        // Print post-order traversal
        System.out.println("Post-order traversal:");
        bst.postOrderTraversal();
        System.out.println();

        // Delete a key
        bst.delete(20);

        // Print in-order traversal after deletion
        System.out.println("In-order traversal after deletion:");
        bst.inOrderTraversal();
        System.out.println();
    }
}
Copy The Code & Try With Live Editor

#3 Binary Search Tree(BST) implement in C

Code - C Programming

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

// Node structure for the Binary Search Tree
struct Node {
    int data;
    struct Node* left;
    struct Node* 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;
}

// Function to insert a value into the BST
struct Node* insert(struct Node* root, int value) {
    // If the tree is empty, create a new node and return it
    if (root == NULL) {
        return createNode(value);
    }

    // Otherwise, recur down the tree
    if (value  <  root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

// Function to perform an in-order traversal of the BST
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// Function to search for a value in the BST
struct Node* search(struct Node* root, int value) {
    // Base Cases: root is null or value is present at root
    if (root == NULL || root->data == value) {
        return root;
    }

    // Value is smaller than root's key
    if (value  <  root->data) {
        return search(root->left, value);
    }

    // Value is larger than root's key
    return search(root->right, value);
}

int main() {
    struct Node* root = NULL;

    // Insert elements into the BST
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    // Print in-order traversal of the BST
    printf("In-order traversal: ");
    inorderTraversal(root);
    printf("\n");

    // Search for a value in the BST
    int searchValue = 40;
    struct Node* result = search(root, searchValue);

    if (result != NULL) {
        printf("%d found in the BST.\n", searchValue);
    } else {
        printf("%d not found in the BST.\n", searchValue);
    }

    return 0;
}
Copy The Code & Try With Live Editor

#4 Binary Search Tree(BST) implement in C++

Code - C++ Programming

#include <iostream>

class TreeNode {
public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
private:
    TreeNode* root;

    // Helper function to insert a value into the tree
    TreeNode* insert(TreeNode* node, int value) {
        if (node == nullptr) {
            return new TreeNode(value);
        }

        if (value  <  node->data) {
            node->left = insert(node->left, value);
        } else if (value > node->data) {
            node->right = insert(node->right, value);
        }

        return node;
    }

    // Helper function to perform in-order traversal
    void inorderTraversal(TreeNode* node) {
        if (node != nullptr) {
            inorderTraversal(node->left);
            std::cout << node->data << " ";
            inorderTraversal(node->right);
        }
    }

public:
    BinarySearchTree() : root(nullptr) {}

    // Function to insert a value into the tree
    void insert(int value) {
        root = insert(root, value);
    }

    // Function to perform in-order traversal of the tree
    void inorderTraversal() {
        inorderTraversal(root);
        std::cout << std::endl;
    }
};

int main() {
    BinarySearchTree bst;

    // Insert values into the tree
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(20);
    bst.insert(40);
    bst.insert(60);
    bst.insert(80);

    // Perform in-order traversal
    std::cout << "In-order traversal: ";
    bst.inorderTraversal();

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Binary Search Tree(BST)-DevsEnv