Binary Search Trees

Overview

A Binary Search Tree (BST) is a hierarchical data structure where each node has at most two children, referred to as the left and right child. The defining characteristic of a BST is that for any node:

• The left subtree contains values less than the node's value.
• The right subtree contains values greater than the node's value. This property makes BSTs highly efficient for searching, insertion, and deletion operations, with average time complexities of O(log n) for balanced trees.

Structure of a BST

• Node: Contains data, a reference to the left child, and a reference to the right child.
• Root: The topmost node of the tree.
• Leaf: A node with no children.
• Subtree: A tree consisting of a node and its descendants.

Creating a Binary Search Tree

Using Object-Oriented Programming (OOP)

A typical BST implementation uses classes to define the structure and behaviour.

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

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

    def insert(self, value):
        if not self.root:
            self.root = TreeNode(value)
        else:
            self._insert(self.root, value)

    def _insert(self, current, value):
        if value < current.value:
            if current.left:
                self._insert(current.left, value)
            else:
                current.left = TreeNode(value)
        else:
            if current.right:
                self._insert(current.right, value)
            else:
                current.right = TreeNode(value)

Traversing a BST

Traversal involves visiting all nodes in a specific order.

Common traversal methods include:

Inorder Traversal (Left, Root, Right):

Visits nodes in ascending order for a BST.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

Preorder Traversal (Root, Left, Right):

Visits nodes in the order they would be created in a depth-first manner.

def preorder(node):
    if node:
        print(node.value, end=" ")
        preorder(node.left)
        preorder(node.right)

Postorder Traversal (Left, Right, Root):

Useful for operations like deleting the tree from leaf to root.

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=" ")

Adding Data to a BST

When inserting data:

1. Start at the root.
2. Compare the value to be inserted with the current node:

• If smaller, move to the left.
• If larger, move to the right.

3. Repeat until an empty position is found.

def insert(node, value):
    if not node:
        return TreeNode(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

Removing Data from a BST

Removing a node requires handling three cases:

4. Node with no children (Leaf Node):

• Simply remove the node.

5. Node with one child:

• Replace the node with its child.

6. Node with two children:

• Replace the node's value with its in-order successor (the smallest value in the right subtree).
• Remove the successor node.

def delete_node(node, value):
    if not node:
        return node
    if value < node.value:
        node.left = delete_node(node.left, value)
    elif value > node.value:
        node.right = delete_node(node.right, value)
    else:
        # Node with only one child or no child
        if not node.left:
            return node.right
        elif not node.right:
            return node.left

        # Node with two children
        temp = min_value_node(node.right)
        node.value = temp.value
        node.right = delete_node(node.right, temp.value)
    return node

def min_value_node(node):
    current = node
    while current.left:
        current = current.left
    return current

Using Arrays (Procedural Approach)

A BST can also be represented indirectly using arrays, but this is less common than using linked structures. Typically, array indices are used to simulate parent-child relationships.

This method is more suitable for Complete Binary Trees.

Examples of Usage

Building a BST and Traversing:

bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(7)

print("Inorder Traversal:")
inorder(bst.root)  # Output: 5 7 10 15

Deleting a Node:

bst.root = delete_node(bst.root, 10)
print("Inorder after deletion:")
inorder(bst.root)  # Output: 5 7 15

Note Summary