Binary Search Tree (BST): Fast Search Using the Left‑Small Right‑Large Rule

What Is a BST?

A binary search tree (BST) builds on a regular binary tree by enforcing the strict rule left subtree nodes < root node < right subtree nodes . This ordering enables efficient lookup, insertion, and deletion.

Three Core BST Properties (Interview Must‑Knows)

Every node satisfies the left‑small right‑large rule.

In‑order traversal of a BST yields a sorted ascending array.

Both left and right subtrees must recursively obey the BST rule.

Why Use a BST? Comparison with an Ordinary Binary Tree

Ordinary binary trees store data unordered, leading to linear‑time search O(n). In contrast, a balanced BST provides logarithmic‑time search O(log n) in the ideal case, making the performance gap grow dramatically as data size increases.

The main drawback is that a degenerate (unbalanced) BST can degrade to a linear chain, which will be addressed in the next episode on balanced trees.

Real‑World Scenarios

Ordered data retrieval and leaderboard ranking.

Underlying concept of database indexes.

Automatic deduplication and ordered insertion.

Foundation for advanced structures such as AVL and red‑black trees.

Common interview problems: two‑sum, BST validation, converting a sorted array to a BST.

Complete Python Implementation (Copy‑Paste Ready)

# Define a BST node
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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

    # 1. Insert node (strict left‑small right‑large rule)
    def insert(self, val):
        def _insert(node, val):
            if not node:
                return TreeNode(val)
            if val < node.val:
                node.left = _insert(node.left, val)
            elif val > node.val:
                node.right = _insert(node.right, val)
            # equal values are ignored (BST deduplication)
            return node
        self.root = _insert(self.root, val)

    # 2. Search for a value
    def search(self, val):
        def _search(node, val):
            if not node:
                return False
            if node.val == val:
                return True
            elif val < node.val:
                return _search(node.left, val)
            else:
                return _search(node.right, val)
        return _search(self.root, val)

    # 3. In‑order traversal (produces sorted result)
    def in_order(self):
        res = []
        def _traverse(node):
            if not node:
                return
            _traverse(node.left)
            res.append(node.val)
            _traverse(node.right)
        _traverse(self.root)
        return res

    # 4. Delete a node (interview hot‑spot)
    def delete(self, val):
        def _delete(node, val):
            if not node:
                return None
            if val < node.val:
                node.left = _delete(node.left, val)
            elif val > node.val:
                node.right = _delete(node.right, val)
            else:
                # Case 1: leaf or single child
                if not node.left:
                    return node.right
                if not node.right:
                    return node.left
                # Case 2: two children – replace with smallest in right subtree
                temp = node.right
                while temp.left:
                    temp = temp.left
                node.val = temp.val
                node.right = _delete(node.right, temp.val)
            return node
        self.root = _delete(self.root, val)

# ===== Test Run =====
if __name__ == "__main__":
    bst = BST()
    nums = [5, 3, 7, 2, 4, 6, 8]
    for num in nums:
        bst.insert(num)
    print("BST in‑order result:", bst.in_order())
    print("Search 4:", bst.search(4))
    print("Search 9:", bst.search(9))
    bst.delete(7)
    print("After deleting 7:", bst.in_order())

Deletion Cases (Must‑Know for Interviews)

Leaf node – remove directly.

Node with a single child – replace the node with its child.

Node with two children – find the minimum value in the right subtree, replace the node's value, then delete that minimum node (standard industry approach).

Common Pitfalls for Beginners

Never violate the left‑small right‑large rule during insert or delete.

Duplicate values are ignored by default, providing automatic deduplication.

Inserting sorted data can create a degenerate (skewed) tree, degrading performance to linear time.

Only in‑order traversal yields a sorted sequence; pre‑order, post‑order, and level‑order are not sorted.

Next Episode Preview

The upcoming ninth episode will cover balanced binary trees (AVL), which automatically maintain balance, prevent skewed trees, and guarantee O(log n) efficiency. It will also introduce red‑black trees as a prerequisite for advanced interview topics.