Binary Search Tree in Python: Insert, Search, and Traverse

A binary search tree (BST) stores values so that every value in the left subtree is smaller than the node and every value in the right subtree is larger. That ordering makes search efficient when the tree stays reasonably balanced.

Define a node

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

Each node stores one value and two child references. An empty child is represented by None.

Insert values

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

root = None
for value in [8, 3, 10, 1, 6, 14]:
    root = insert(root, value)

The equal-value case above ignores duplicates. Other designs count duplicates or consistently place them on one side; choose one rule and keep it consistent.

Search the tree

def contains(root, target):
    if root is None:
        return False
    if target == root.value:
        return True
    if target < root.value:
        return contains(root.left, target)
    return contains(root.right, target)

print(contains(root, 6))   # True
print(contains(root, 12))  # False

At each node, half of the remaining search space is discarded—provided the tree is balanced.

Inorder traversal gives sorted output

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.value] + inorder(root.right)

print(inorder(root))
# [1, 3, 6, 8, 10, 14]

This is the key BST property: an inorder traversal visits values in ascending order. In production code, use a generator for large trees so you do not create many intermediate lists.

Delete a node

Deletion is the operation interviewers actually probe, because it has three cases: a leaf just disappears, a node with one child is replaced by that child, and a node with two children is replaced by its inorder successor — the smallest value in its right subtree — which preserves the ordering.

def delete(root, value):
    if root is None:
        return None
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        # found it — handle the three cases
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.value = successor.value
        root.right = delete(root.right, successor.value)
    return root

root = delete(root, 3)
print(inorder(root))
# [1, 6, 8, 10, 14]

Note the same pattern as insert: every recursive call's result is assigned back (root.left = ...), and the function returns the possibly-new subtree root. Forgetting either half of that pattern is the classic deletion bug.

Does Python have a built-in BST?

No — the standard library ships bisect (binary search over a sorted list) and heapq (heaps), but no tree. For production code that needs sorted-order operations, the pragmatic answer is sortedcontainers.SortedList; the hand-built BST above is what interviews and data-structures courses expect you to produce.

Complexity and the worst case

For a balanced BST, insert and search are O(log n) on average. If values arrive already sorted, the tree can collapse into a linked list and both operations become O(n). That is why production systems often use self-balancing trees or a database index rather than a hand-built unbalanced BST.

Common interview mistakes

• Forgetting to return the new root after inserting into an empty subtree.
• Searching both branches instead of using the ordering property.
• Claiming every BST operation is O(log n) without mentioning the unbalanced worst case.
• Returning preorder or postorder output when the question asks for sorted values.
• Mutating a node but forgetting to assign it back to root.left or root.right.

Go deeper

The binary search trees lesson turns this article into graded practice: you implement insert, contains, inorder, and delete yourself and an automatic checker verifies each one. If trees are new, the graph representations lesson covers the adjacent ideas.

Practise it: paste the code above into the free browser editor and break it — insert sorted input, watch it degenerate, then fix it. Or start the Python track from lesson one.