Binary Search Tree in Python From Scratch

A binary search tree (BST) is a binary tree with one extra rule that makes searching fast: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. To look for a value you compare it with the current node and go left or right, throwing away half of the remaining tree at each step, just as in binary search on a sorted list.

This guide builds a BST in Python from scratch: insert, search, inorder traversal and delete. Then it covers the questions interviewers love, and the one thing that can make a BST slow, which is losing its balance. All the output shown is real.

The BST rule

Here is a BST built from the values 50, 30, 70, 20, 40, 60, 80:

        50
       /  \
     30    70
    / \   / \
   20 40 60 80

Look at any node, for example 30. Everything to its left (20) is smaller, and everything to its right (40) is larger. The same holds for 50: the whole left side (30, 20, 40) is smaller and the whole right side (70, 60, 80) is larger. The rule is about entire subtrees, not just direct children, and that detail matters later.

Insert, search and inorder

Insert walks down from the root like a search would, and places the new value where the search falls off the tree. Searching does the same and stops when it finds the value. No recursion is needed. Duplicates are ignored here, which is a common choice:

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        node = self.root
        while True:
            if value < node.value:
                if node.left is None:
                    node.left = Node(value)
                    return
                node = node.left
            elif value > node.value:
                if node.right is None:
                    node.right = Node(value)
                    return
                node = node.right
            else:
                return                      # duplicates are ignored

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

    def inorder(self):
        def walk(node):
            if node:
                yield from walk(node.left)
                yield node.value
                yield from walk(node.right)
        return list(walk(self.root))

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)

print(tree.inorder())
print(tree.contains(60), tree.contains(65))
print(tree.root.value, tree.root.left.value, tree.root.right.value)

Output

[20, 30, 40, 50, 60, 70, 80]
True False
50 30 70

The inorder result is sorted, which follows straight from the rule: all smaller values, then the node, then all larger values. That is the reason an inorder traversal of a BST is worth knowing (see the traversals in Binary Tree in Python: Traversals Explained).

The insertion order changes the shape

The same three values inserted in a different order give a different tree, even though both are valid BSTs and read the same in sorted order. The first value inserted always becomes the root:

a, b = BST(), BST()
for v in [50, 30, 70]:
    a.insert(v)
for v in [70, 30, 50]:
    b.insert(v)
print(a.inorder(), b.inorder())
print(a.root.value, b.root.value)

Output

[30, 50, 70] [30, 50, 70]
50 70

That is important, since the shape decides how fast the tree is, as we will see below.

Deleting a node (3 cases)

Deleting is the hardest operation, because the rule must still hold afterwards. There are three cases:

1. Leaf (no children): just remove it.
2. One child: replace the node with its child.
3. Two children: replace the node’s value with its inorder successor, the smallest value in its right subtree, and then delete that successor from the right subtree. The successor is the next larger value, so it fits in the same place without breaking the rule.

Add these two methods inside the BST class:

    def delete(self, value):
        self.root = self._delete(self.root, value)

    def _delete(self, node, value):
        if node is None:
            return None
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            if node.left is None:           # no child, or only a right child
                return node.right
            if node.right is None:          # only a left child
                return node.left
            successor = node.right          # two children: smallest value on the right
            while successor.left:
                successor = successor.left
            node.value = successor.value
            node.right = self._delete(node.right, successor.value)
        return node

Now we delete a leaf (20), a node with one child (60, which has 65) and finally the root, which has two children:

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80, 65]:
    tree.insert(v)
print(tree.inorder())

tree.delete(20)                  # a leaf
print(tree.inorder())
tree.delete(60)                  # one child (65)
print(tree.inorder())
tree.delete(50)                  # two children, and it is the root
print(tree.inorder(), "root:", tree.root.value)

Output

[20, 30, 40, 50, 60, 65, 70, 80]
[30, 40, 50, 60, 65, 70, 80]
[30, 40, 50, 65, 70, 80]
[30, 40, 65, 70, 80] root: 65

The root 50 was replaced by 65, the smallest value on its right side, and the tree still reads in sorted order.

Why balance matters

A search takes as many steps as the tree is tall. If you insert values that are already sorted, every new value goes to the right of the previous one, and the tree turns into a chain, which is a linked list in disguise. We count steps rather than time, so the result is the same on every computer:

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

def search_steps(tree, value):
    steps, node = 0, tree.root
    while node:
        steps += 1
        if value == node.value:
            break
        node = node.left if value < node.value else node.right
    return steps

sorted_tree, mixed_tree = BST(), BST()
for v in range(1, 16):
    sorted_tree.insert(v)
for v in [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]:
    mixed_tree.insert(v)

print("same 15 values")
print("height, inserted in order   :", height(sorted_tree.root))
print("height, inserted in a mix   :", height(mixed_tree.root))
print("steps to find 15, in order  :", search_steps(sorted_tree, 15))
print("steps to find 15, in a mix  :", search_steps(mixed_tree, 15))

Output

same 15 values
height, inserted in order   : 15
height, inserted in a mix   : 4
steps to find 15, in order  : 15
steps to find 15, in a mix  : 4

Fifteen steps to find one value in a 15-node tree, compared with 4. With a million nodes it is a million steps against about 20. This is why real systems use self-balancing trees (AVL trees and red-black trees), which rotate nodes after each insert to keep the height near log n. You will rarely write one, but you should know why they exist.

Validating a BST

“Check whether this tree is a valid BST” is a top interview question, and it has a tempting wrong answer: checking that each node is larger than its left child and smaller than its right child. That misses the fact that the rule covers whole subtrees. In the tree below, every parent-child pair looks fine, but 4 sits in the right subtree of 5, so the tree is not a BST:

      5
     / \
    1   6
       / \
      4   7

def naive_valid(node):
    if node is None:
        return True
    if node.left and node.left.value >= node.value:
        return False
    if node.right and node.right.value <= node.value:
        return False
    return naive_valid(node.left) and naive_valid(node.right)

def is_valid(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not (low < node.value < high):
        return False
    return (is_valid(node.left, low, node.value)
            and is_valid(node.right, node.value, high))

root = Node(5)
root.left = Node(1)
root.right = Node(6)
root.right.left = Node(4)         # smaller than 5, but on the right of 5
root.right.right = Node(7)

print(naive_valid(root), is_valid(root))

good = BST()
for v in [5, 1, 6, 7]:
    good.insert(v)
print(is_valid(good.root))

Output

True False
True

The correct version passes down a range. Every node must be strictly between low and high. Going left, the current value becomes the new upper limit. Going right, it becomes the new lower limit. (Another valid approach: do an inorder traversal and check that the values are strictly increasing.)

Kth smallest and lowest common ancestor

Two more problems become easy once you use the BST rule. The kth smallest value is the kth item of the inorder sequence, so we do an iterative inorder walk (with a stack, see Stack in Python) and stop after k items:

def kth_smallest(root, k):
    stack, node = [], root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.value
        node = node.right

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)
print(kth_smallest(tree.root, 1), kth_smallest(tree.root, 3), kth_smallest(tree.root, 7))

Output

20 40 80

The lowest common ancestor of two values is the first node where they split: one goes left and one goes right, or one of them is the node itself. In a BST you can find it by walking down once:

def lowest_common_ancestor(root, p, q):
    node = root
    while node:
        if p < node.value and q < node.value:
            node = node.left
        elif p > node.value and q > node.value:
            node = node.right
        else:
            return node.value

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)
print(lowest_common_ancestor(tree.root, 20, 40))
print(lowest_common_ancestor(tree.root, 20, 80))
print(lowest_common_ancestor(tree.root, 60, 80))

Output

30
50
70

Time complexity

Everything except a full traversal follows one path from the root down, so the cost is the tree’s height: log n when it is balanced, and n when it is a chain. See Big O Notation in Python for what these mean.

BST vs what Python gives you

Python has no built-in BST. If you need to keep values in order, there are simpler options. A dict or set gives O(1) lookup when order does not matter (see Hash Table in Python). When you need a sorted sequence and searches by position, the bisect module keeps a plain list sorted:

import bisect

data = []
for v in [50, 30, 70, 20, 40]:
    bisect.insort(data, v)
print(data)
print(bisect.bisect_left(data, 40))
print(data[0], data[-1])

Output

[20, 30, 40, 50, 70]
2
20 70

A sorted list finds a value in O(log n) with bisect, but inserting into the middle costs O(n) because items shift. A balanced BST does both in O(log n), which matters only for very large, constantly changing data. For the smallest-first case, use a heap (Heap and heapq in Python). The BST is mostly an interview topic and a way to understand ordered data.

Common mistakes

• Checking only parent and child when validating. Pass a low and high range down instead.
• Forgetting the two-children case in delete. Replace the value with the inorder successor, then delete the successor.
• Forgetting to reassign the child. Recursive delete must return the node and be assigned back: node.left = self._delete(node.left, value).
• Assuming a BST is always fast. Sorted input builds a chain. Shuffle the input, or use a self-balancing tree.
• Ignoring duplicates. Decide whether to skip them, count them or send them to one side, and be consistent.
• Confusing “smaller than the parent” with “smaller than everything above”. Every value must fit all its ancestors.

Try it yourself

Work out each answer first, then open the solution. The BST class from above is assumed.

1. Find the smallest value in a BST without visiting every node.

def minimum(root):
    node = root
    while node.left:
        node = node.left
    return node.value

tree = BST()
for v in [50, 30, 70, 20, 40]:
    tree.insert(v)
print(minimum(tree.root))

20

2. Return the sum of all values between low and high (inclusive).

def range_sum(node, low, high):
    if node is None:
        return 0
    if node.value < low:
        return range_sum(node.right, low, high)
    if node.value > high:
        return range_sum(node.left, low, high)
    return (node.value
            + range_sum(node.left, low, high)
            + range_sum(node.right, low, high))

tree = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(v)
print(range_sum(tree.root, 30, 60))

180

3. When deleting a node with two children, why do we use the smallest value of the right subtree?

4. You insert the numbers 1 to 1000 in increasing order into a BST. How many steps does a search for 1000 take?

Run these in our free Python compiler.

Frequently asked questions

What is a binary search tree in Python?

A binary search tree is a binary tree in which every node’s left subtree holds smaller values and its right subtree holds larger values. Python has no built-in BST, so you write a Node class and a small BST class.

What is the time complexity of a binary search tree?

Search, insert and delete take O(h), where h is the height of the tree: O(log n) for a balanced tree, and O(n) for a degenerate one that looks like a linked list.

How do you delete a node from a BST?

There are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children takes the value of its inorder successor (the smallest value in the right subtree), and then that successor is deleted.

How do you check if a tree is a valid BST?

Pass a valid range down the tree: every node must be greater than low and smaller than high. Checking only the parent and its children is not enough. You can also check that an inorder traversal is strictly increasing.

Why does inorder traversal of a BST give sorted order?

Because it visits the left subtree first (all smaller values), then the node, then the right subtree (all larger values), and that holds at every level.

Is there a built-in BST in Python?

No. The standard library gives you dict, set, heapq and bisect for related jobs. Third-party packages such as sortedcontainers provide ordered collections.

Related reading

• Binary Tree in Python: Traversals Explained – the tree basics this post builds on.
• Binary Search in Python: 3 Common Variations – the same halving idea on a sorted list.
• Heap and heapq in Python: Priority Queues – when you only need the smallest item.
• Big O Notation Explained With Python Examples – what O(log n) and O(n) really mean.