Binary Search Trees#

Welcome to Day 15 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive into Binary Search Trees (BST), a powerful data structure that combines the efficiency of binary search with the flexibility of a linked data structure.

What is a Binary Search Tree?#

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

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.

These properties make BSTs efficient for search, insertion, and deletion operations.

Implementing a Binary Search Tree in Python#

Let’s implement a basic Binary Search Tree:

 1class BSTNode:
 2    def __init__(self, key):
 3        self.key = key
 4        self.left = None
 5        self.right = None
 6
 7class BinarySearchTree:
 8    def __init__(self):
 9        self.root = None
10
11    def insert(self, key):
12        self.root = self._insert_recursive(self.root, key)
13
14    def _insert_recursive(self, root, key):
15        if root is None:
16            return BSTNode(key)
17        if key < root.key:
18            root.left = self._insert_recursive(root.left, key)
19        else:
20            root.right = self._insert_recursive(root.right, key)
21        return root
22
23    def search(self, key):
24        return self._search_recursive(self.root, key)
25
26    def _search_recursive(self, root, key):
27        if root is None or root.key == key:
28            return root
29        if key < root.key:
30            return self._search_recursive(root.left, key)
31        return self._search_recursive(root.right, key)
32
33    def inorder_traversal(self):
34        self._inorder_recursive(self.root)
35
36    def _inorder_recursive(self, root):
37        if root:
38            self._inorder_recursive(root.left)
39            print(root.key, end=" ")
40            self._inorder_recursive(root.right)
41
42# Example usage
43bst = BinarySearchTree()
44keys = [50, 30, 70, 20, 40, 60, 80]
45
46for key in keys:
47    bst.insert(key)
48
49print("Inorder traversal of the BST:")
50bst.inorder_traversal()

BST Operations#

1. Insertion#

The insertion operation in a BST maintains the BST property:

• If the tree is empty, create a new node and set it as the root.
• Otherwise, compare the key with the root:
  • If the key is less than the root, insert it into the left subtree.
  • If the key is greater than the root, insert it into the right subtree.
• Repeat this process recursively until you find an empty spot.

Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).

2. Search#

Searching in a BST is efficient due to its structure:

• Start at the root.
• If the key matches the current node, return the node.
• If the key is less than the current node, search in the left subtree.
• If the key is greater than the current node, search in the right subtree.
• Repeat until you find the key or reach a leaf node.

Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).

3. Deletion#

Deleting a node from a BST is more complex and involves three cases:

1. Node to be deleted is a leaf: Simply remove it.
2. Node has one child: Replace the node with its child.
3. Node has two children: Find the inorder successor (minimum value in the right subtree), replace the node’s value with the successor’s value, and delete the successor.

Let’s implement the deletion operation:

 1class BinarySearchTree:
 2    # ... (previous methods remain the same)
 3
 4    def delete(self, key):
 5        self.root = self._delete_recursive(self.root, key)
 6
 7    def _delete_recursive(self, root, key):
 8        if root is None:
 9            return root
10
11        if key < root.key:
12            root.left = self._delete_recursive(root.left, key)
13        elif key > root.key:
14            root.right = self._delete_recursive(root.right, key)
15        else:
16            # Node with only one child or no child
17            if root.left is None:
18                return root.right
19            elif root.right is None:
20                return root.left
21
22            # Node with two children
23            root.key = self._min_value(root.right)
24            root.right = self._delete_recursive(root.right, root.key)
25
26        return root
27
28    def _min_value(self, node):
29        current = node
30        while current.left is not None:
31            current = current.left
32        return current.key
33
34# Example usage
35bst = BinarySearchTree()
36keys = [50, 30, 70, 20, 40, 60, 80]
37
38for key in keys:
39    bst.insert(key)
40
41print("Original BST:")
42bst.inorder_traversal()
43
44bst.delete(30)
45print("\nBST after deleting 30:")
46bst.inorder_traversal()

Time Complexity: O(h), where h is the height of the tree. In a balanced BST, this is O(log n).

Balancing Binary Search Trees#

The efficiency of BST operations depends on the height of the tree. In the worst case, when the tree becomes skewed (essentially a linked list), the time complexity degrades to O(n).

To maintain efficiency, we use self-balancing BSTs such as:

1. AVL Trees
2. Red-Black Trees

These structures automatically keep the tree balanced after insertions and deletions, ensuring O(log n) time complexity for basic operations.

Applications of Binary Search Trees#

1. Implementing associative arrays (dictionaries)
2. Database indexing
3. Implementing priority queues
4. Syntax trees in compilers
5. Searching algorithms

Exercise#

1. Implement a function to find the kth smallest element in a BST.
2. Create a method to check if a binary tree is a valid BST.
3. Implement a function to find the lowest common ancestor of two nodes in a BST.

Summary#

Binary Search Trees are powerful data structures that provide efficient searching, insertion, and deletion operations. They form the basis for more advanced self-balancing trees and are crucial in many applications requiring fast look-up, addition, and removal of ordered data.

Understanding BSTs is essential for tackling more complex tree-based problems and is often a prerequisite for advanced algorithms involving balanced trees and tree-based data structures.

Tomorrow, we’ll explore tree traversal techniques in more depth, including both recursive and iterative approaches. Stay tuned!

Solution#

 1def kth_smallest(root, k):
 2    stack = []
 3    current = root
 4    while stack or current:
 5        while current:              # go as far left as possible
 6            stack.append(current)
 7            current = current.left
 8        current = stack.pop()
 9        k -= 1
10        if k == 0:
11            return current.key
12        current = current.right     # then explore the right subtree
13    return None
14
15
16def is_valid_bst(root, low=float("-inf"), high=float("inf")):
17    if root is None:
18        return True
19    if not (low < root.key < high):
20        return False
21    return (is_valid_bst(root.left, low, root.key)
22            and is_valid_bst(root.right, root.key, high))
23
24
25def lowest_common_ancestor(root, a, b):
26    current = root
27    while current:
28        if a < current.key and b < current.key:
29            current = current.left
30        elif a > current.key and b > current.key:
31            current = current.right
32        else:
33            return current          # split point is the LCA
34    return None