Python Binary Search Trees

Python Binary Search Trees (BST)

A Binary Search Tree (BST) is a special type of binary tree that satisfies the binary search property. This property makes searching for elements incredibly efficient.

The properties of a Binary Search Tree are:

1. The left subtree of a node contains only nodes with keys lesser than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. The left and right subtrees must also be binary search trees.
4. There must be no duplicate nodes.

!Binary Search Tree Diagram

Advantages of BST

The primary advantage of a BST is its efficiency. Because the tree is always sorted, operations like searching, insertion, and deletion can be performed very quickly.

• Search: O(log n) on average.
• Insertion: O(log n) on average.
• Deletion: O(log n) on average.

Implementing a BST in Python

We can implement a BST with insert and search methods. We'll use the same Node class from the previous chapter.

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

// Function to insert a new node with a given key
def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root
// Function to search a given key in BST
def search(root, key):
    // Base Cases: root is null or key is present at root
    if root is None or root.val == key:
        return root
    // Key is greater than root's key
    if root.val < key:
        return search(root.right, key)
    // Key is smaller than root's key
    return search(root.left, key)
// --- Usage ---
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)
// Search for 60
result = search(r, 60)
if result:
    print("Found key 60 in the BST")
else:
    print("Key 60 not found")

In-order Traversal of a BST

A key feature of BSTs is that an in-order traversal (Left, Root, Right) visits the nodes in ascending sorted order.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)

// Using the tree from the previous example
print("Sorted output using in-order traversal:")
inorder(r) // Output: 20 30 40 50 60 70 80