Python Implementation of Binary Search Tree (BST) – Concepts, Core Operations, and Applications

Today we present a Python version of the Binary Search Tree (BST), a magical data structure that automatically sorts data and offers fast lookup.

What is a Binary Search Tree?

Imagine arranging books on a shelf by their numbers: books with smaller numbers go to the left, larger numbers to the right, and every node follows this rule.

Values smaller than the current node go to the left child.

Values larger than the current node go to the right child.

All nodes obey this ordering.

This is the core idea of a BST.

Python Implementation of the Node Class

The Python definition of a BST node is concise compared with C++:

<code>class TreeNode:
    def __init__(self, val):
        self.val = val  # node value
        self.left = None  # left child (smaller values)
        self.right = None  # right child (larger values)
</code>

Three Core Operations (Python)

1. Search – Faster than a dictionary

<code>def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)  # go left
    return search(root.right, val)   # go right
</code>

Explanation: Each comparison discards half of the remaining nodes, similar to a binary search.

2. Insert – Automatically finds the correct position

<code>def insert(root, val):
    if not root:
        return TreeNode(val)  # create a new node
    if val < root.val:
        root.left = insert(root.left, val)   # go left
    elif val > root.val:
        root.right = insert(root.right, val) # go right
    return root
</code>

3. Delete – Handles three cases

<code>def delete(root, val):
    if not root:
        return root
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Case 1: node has at most one child
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Case 2: node has two children – replace with inorder successor
        temp = find_min(root.right)
        root.val = temp.val
        root.right = delete(root.right, temp.val)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node
</code>

Performance Comparison

Operation

Balanced Tree (Best)

Degenerate Tree (Worst)

Search

O(log n) 🚀

O(n) 🐢

Insert

O(log n) ⚡

O(n) 🐌

Delete

O(log n) ✈️

O(n) 🚶

Note: If a BST becomes unbalanced, performance degrades dramatically, just like a queue with a line‑cutting intruder.

Practical Application Scenarios

Database Systems: MySQL indexes are an advanced form of BST.

Game Development: Fast lookup of game object positions.

File Systems: Hierarchical directory structures.

Auto‑completion: Predictive text in input methods.

Exercise Questions

How would you write an inorder traversal of a BST in Python? What is the characteristic of its output?

How can you verify whether a binary tree satisfies the BST property?

When would you prefer a BST over a Python dict?

<code># Inorder traversal template
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)
</code>

Answer: An inorder traversal of a BST yields the node values in ascending order, effectively flattening the tree.

For further learning, scan the QR code below to receive free Python course materials, including e‑books, tutorials, project templates, and source code.

Recommended reading:

Very useful Python libraries – one hit and they catch fire!

Implement a desktop pet with Python

uv: Unified Python package management

Python and Big Data: Introduction to PySpark