B4.1.4 Explain the structures and properties of BSTs. (HL only)

The big idea

A Binary Search Tree (BST) is a hierarchical data structure that stores elements (nodes) in a way that makes searching, insertion, and deletion efficient.

Each node in a BST has:

• A key (data value)
• A pointer to a left child (all keys smaller than the current node’s key)
• A pointer to a right child (all keys larger than the current node’s key)

This structure ensures that:

• Searching is fast (O(log n) on average) because each comparison halves the search space.
• Data remains sorted without additional processing.

 

1. Structure and properties of a BST

1. Binary property:
   Each node has at most two children.
2. Search property:
   For any node:
   • Left subtree contains keys less than the node’s key.
   • Right subtree contains keys greater than the node’s key.
3. No duplicates:
   Typically, each key appears only once (though variants exist for duplicates).

 

2. BST in Python

Node structure:

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

BST class with basic operations:

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

    # Insertion
    def insert(self, key):
        self.root = self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if not node:
            return Node(key)
        if key < node.key:
            node.left = self._insert_recursive(node.left, key)
        elif key > node.key:
            node.right = self._insert_recursive(node.right, key)
        return node

    # Searching
    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        if not node:
            return False
        if key == node.key:
            return True
        elif key < node.key:
            return self._search_recursive(node.left, key)
        else:
            return self._search_recursive(node.right, key)

    # Traversal (in-order)
    def inorder(self):
        self._inorder_recursive(self.root)
        print()

    def _inorder_recursive(self, node):
        if node:
            self._inorder_recursive(node.left)
            print(node.key, end=" ")
            self._inorder_recursive(node.right)

    # Deletion
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if not node:
            return node
        if key < node.key:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.key:
            node.right = self._delete_recursive(node.right, key)
        else:
            # Node with one child or no child
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            # Node with two children: Get inorder successor
            temp = self._min_value_node(node.right)
            node.key = temp.key
            node.right = self._delete_recursive(node.right, temp.key)
        return node

    def _min_value_node(self, node):
        current = node
        while current.left:
            current = current.left
        return current

 

3. Example usage

bst = BST()
for key in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(key)

print("In-order traversal (sorted):")
bst.inorder()  # 20 30 40 50 60 70 80

print("Search 40:", bst.search(40))  # True
print("Search 90:", bst.search(90))  # False

bst.delete(20)  # Leaf node
bst.delete(30)  # Node with one child
bst.delete(50)  # Node with two children

print("In-order after deletions:")
bst.inorder()  # 40 60 70 80

 

4. Traversal methods

BSTs can be traversed in several ways:

• In-order (Left → Root → Right): Produces sorted order.
• Pre-order (Root → Left → Right): Useful for saving tree structure.
• Post-order (Left → Right → Root): Useful for deletion or freeing memory.

 

5. BST sketch example

For the insertion sequence:

50, 30, 70, 20, 40, 60, 80

The BST diagram looks like:

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

---

Advantages

• Efficient search, insert, delete (O(log n) average case).
• Keeps data sorted without extra sorting step.
• Flexible for ordered operations.

Disadvantages

• Worst-case performance O(n) if the tree becomes unbalanced (e.g., inserting sorted data into an unbalanced BST).
• Requires balancing techniques (AVL, Red-Black Trees) for consistent performance.