Python Program to Implement a Binary Search Tree (BST)

A Binary Search Tree (BST) is one of the most common data structures asked about in coding interviews, and it's the foundation for more advanced structures like balanced trees (AVL, Red-Black) and database indexes. In a BST, every node's left subtree holds smaller values and its right subtree holds larger values, which makes searching, inserting, and sorted traversal all efficient.

In this post we build a BST in Python from scratch with a Node class and a BinarySearchTree class that supports insert and an in-order traversal that prints the values in sorted order.

Python Program to Implement a Binary Search Tree

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


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_recursive(self.root, value)

    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_recursive(node.right, value)

    def in_order(self, node, result=None):
        if result is None:
            result = []
        if node:
            self.in_order(node.left, result)
            result.append(node.value)
            self.in_order(node.right, result)
        return result

    def search(self, value):
        current = self.root
        while current:
            if value == current.value:
                return True
            current = current.left if value < current.value else current.right
        return False


# Demo
bst = BinarySearchTree()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.insert(v)

print("In-order (sorted):", bst.in_order(bst.root))
print("Search 40:", bst.search(40))
print("Search 99:", bst.search(99))

Output:

In-order (sorted): [20, 30, 40, 50, 60, 70, 80]
Search 40: True
Search 99: False

Because every insert and search moves either left or right based on a single comparison, both operations run in O(log n) time on a balanced tree — but note that a BST built from already-sorted input degenerates into a plain linked list with O(n) operations, which is why self-balancing variants like AVL trees exist in production systems. This implementation is a good base before moving on to deletion, height-balancing, or level-order traversal with BFS.

---