BST

A binary search tree (BST) is a binary tree data structure in which each vertex has at most two children, referred to as the left and right child.
In a BST, the key values of vertices in the left subtree are less than the key value of the root, and the key values of nodes in the right subtree are greater than the key value of the root. This property allows for efficient search, insertion, and deletion operations, making BSTs useful for implementing algorithms such as binary search and various data structures like sets and maps.

BST implementation

python
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class TreeNode:
    def __init__(self, key):
        # Initialize a new TreeNode with a given key value
        self.key = key
        self.left = None  # Initialize left child pointer to None
        self.right = None  # Initialize right child pointer to None

class BST:
    def __init__(self):
        # Initialize an empty Binary Search Tree (BST) with no root
        self.root = None

    def insert(self, key):
        # Insert a new key into the BST
        if self.root is None:  # If the tree is empty, create a new root node
            self.root = TreeNode(key)
        else:
            self._insert_recursive(self.root, key)  # Otherwise, call recursive insertion

    def _insert_recursive(self, root, key):
        # Recursively insert the key into the appropriate position in the tree
        if key < root.key:  # If the key is less than the current node's key, go left
            if root.left is None:  # If the left child is None, insert a new node
                root.left = TreeNode(key)
            else:
                self._insert_recursive(root.left, key)  # Otherwise, continue recursion to the left
        elif key > root.key:  # If the key is greater than the current node's key, go right
            if root.right is None:  # If the right child is None, insert a new node
                root.right = TreeNode(key)
            else:
                self._insert_recursive(root.right, key)  # Otherwise, continue recursion to the right

    def delete(self, key):
        # Delete a key from the BST
        self.root = self._delete_recursive(self.root, key)  # Call recursive deletion

    def _delete_recursive(self, root, key):
        # Recursively delete the key from the tree
        if root is None:  # If the tree is empty or key not found, return None
            return root
        if key < root.key:  # If the key is less than the current node's key, go left
            root.left = self._delete_recursive(root.left, key)  # Recursively delete from the left subtree
        elif key > root.key:  # If the key is greater than the current node's key, go right
            root.right = self._delete_recursive(root.right, key)  # Recursively delete from the right subtree
        else:  # Key found, perform deletion
            if root.left is None:  # If the left child is None, return the right child
                return root.right
            elif root.right is None:  # If the right child is None, return the left child
                return root.left
            else:  # Node has both children, find successor and replace key with successor
                successor = self._find_min(root.right)
                root.key = successor.key
                root.right = self._delete_recursive(root.right, successor.key)
        return root

    def search(self, key):
        # Search for a key in the BST
        return self._search_recursive(self.root, key)  # Call recursive search

    def _search_recursive(self, root, key):
        # Recursively search for the key in the tree
        if root is None or root.key == key:  # If root is None or key found, return root
            return root
        if key < root.key:  # If the key is less than the current node's key, search left subtree
            return self._search_recursive(root.left, key)
        return self._search_recursive(root.right, key)  # Otherwise, search right subtree

Basic operations time complexity

Note

A balanced tree is a data structure in which the heights of the subtrees of any node differ by at most one. We will discuss it in more detail in the next sections.

1. Insertion:

   • Best and Average Case (O(log n)): In a balanced BST, insertion involves traversing down the tree from the root to find the appropriate position for the new node. At each level, the search space is divided in half, reducing the search time logarithmically with respect to the number of nodes;

   • Worst Case (O(n)): If the tree becomes unbalanced, such as when nodes are inserted in sorted order, the tree can degenerate into a linked list. In this case, the insertion operation becomes linear with respect to the number of nodes, as each new node is simply appended to the end of the list.

2. Deletion:

   • Best and Average Case (O(log n)): Similar to insertion, deletion in a balanced BST involves traversing down the tree to find the node to be deleted. The search space is divided in half at each level, resulting in a logarithmic time complexity;

   • Worst Case (O(n)): As with insertion, if the tree becomes unbalanced, deletion can degrade to O(n) time complexity. For example, deleting a node from a skewed tree may require traversing through most or all of the nodes.

3. Search:

   • Best and Average Case (O(log n)): The BST's structure allows for efficient search by recursively traversing down the tree from the root. The search space is halved at each level, leading to a logarithmic time complexity;

   • Worst Case (O(n)): In the worst case scenario, the tree is unbalanced, resulting in a linear search time. This occurs when the tree degenerates into a linked list, and the search traverses through most or all of the nodes.