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.

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.

Practise it: Run your first Python lesson on PyRun, then use the browser editor to implement insert, contains, and inorder yourself.