Binary Search Tree

How Binary Search Tree Works

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

• 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 the left and right subtrees must also be binary search trees

Key operations:

• Insertion: O(log n) average case, O(n) worst case
• Search: O(log n) average case, O(n) worst case
• Deletion: O(log n) average case, O(n) worst case

BSTs are useful for maintaining a sorted collection of elements with efficient insertion, deletion, and lookup operations. However, they can become unbalanced, leading to worst-case performance. Balanced variants like AVL trees and Red-Black trees address this issue.

class Node:
    value
    left
    right

class BST:
    root

    function insert(value):
        root = insertRecursive(root, value)
        visualize()

    function insertRecursive(node, value):
        if node is null:
            return new Node(value)
        if value < node.value:
            node.left = insertRecursive(node.left, value)
        else if value > node.value:
            node.right = insertRecursive(node.right, value)
        return node

    function search(value):
        return searchRecursive(root, value)

    function searchRecursive(node, value):
        if node is null or node.value == value:
            return node
        if value < node.value:
            return searchRecursive(node.left, value)
        return searchRecursive(node.right, value)