Skip to content
Laviyx Learn

Try

DSA course menu

Binary Search Trees (BST) in Python: Insert, Search and Delete

Learn binary search trees: the BST property, searching and inserting in O(h), deleting nodes with zero, one or two children, validating a BST, and why unbalanced BSTs become slow.

Intermediate15 min readUpdated
On this page

A binary search tree (BST) is a binary tree with one rule, the BST property: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.

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

That rule turns every step down the tree into a binary search decision: smaller goes left, larger goes right.

Search and insert#

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

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                       # duplicates are ignored

def search(root, value):
    steps = 0
    while root:
        steps += 1
        if value == root.value:
            return True, steps
        root = root.left if value < root.value else root.right
    return False, steps

def inorder(node):
    return inorder(node.left) + [node.value] + inorder(node.right) if node else []

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

print(inorder(root))
print(search(root, 60))
print(search(root, 65))
Output
[20, 30, 40, 50, 60, 70, 80]
(True, 3)
(False, 3)

An inorder traversal of a BST always comes out sorted. Search and insert follow one path from the root, so they cost O(h), where h is the height.

Minimum, maximum and successor#

The smallest value is reached by going left until you cannot; the largest by going right:

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

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

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

def maximum(node):
    while node.right:
        node = node.right
    return node.value

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print(minimum(root), maximum(root), minimum(root.right))
Output
20 80 60

minimum(root.right) is the inorder successor of the root: the next larger value. Deletion uses it.

Deleting a node#

There are three cases:

  1. No children: just remove it.
  2. One child: replace the node with its child.
  3. Two children: copy the inorder successor (smallest value in the right subtree) into the node, then delete the successor from the right subtree. The successor has no left child, so that second delete is case 1 or 2.
Python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = self.right = None

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

def inorder(node):
    return inorder(node.left) + [node.value] + inorder(node.right) if node else []

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:
        if root.left is None:          # cases 1 and 2
            return root.right
        if root.right is None:
            return root.left
        successor = root.right         # case 3
        while successor.left:
            successor = successor.left
        root.value = successor.value
        root.right = delete(root.right, successor.value)
    return root

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)

root = delete(root, 20)      # leaf
print(inorder(root))
root = delete(root, 30)      # one child (40)
print(inorder(root))
root = delete(root, 50)      # two children: replaced by 60
print(inorder(root), "root is now", root.value)
Output
[30, 40, 50, 60, 70, 80]
[40, 50, 60, 70, 80]
[40, 60, 70, 80] root is now 60

Validating a BST#

Checking only that each node is bigger than its left child and smaller than its right child is not enough: a value deep in the left subtree could still be larger than the root. Pass down the allowed range instead:

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

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

good = Node(50, Node(30, Node(20), Node(40)), Node(70))
sneaky = Node(50, Node(30, Node(20), Node(55)), Node(70))   # 55 is in the left subtree of 50
print(is_bst(good), is_bst(sneaky))
Output
True False

In the second tree, 55 is larger than its parent 30, which looks fine locally, but it sits in the left subtree of 50 and so breaks the rule.

The height problem#

A BST is only fast if it stays short. Inserting values that are already sorted makes every node a right child: the tree becomes a linked list and every operation is O(n).

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

def insert(root, value):
    if root is None:
        return Node(value)
    node = root
    while True:
        if value < node.value:
            if node.left is None:
                node.left = Node(value); break
            node = node.left
        else:
            if node.right is None:
                node.right = Node(value); break
            node = node.right
    return root

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

import random
random.seed(5)
values = list(range(500))

sorted_root = None
for v in values:
    sorted_root = insert(sorted_root, v)

random.shuffle(values)
random_root = None
for v in values:
    random_root = insert(random_root, v)

print("height after sorted inserts:", height(sorted_root))
print("height after shuffled inserts:", height(random_root))
Output
height after sorted inserts: 499
height after shuffled inserts: 18

Self-balancing trees fix this by restructuring as they go; see Balanced Trees (AVL).

OperationBalanced BSTDegenerate BST
search, insert, deleteO(log n)O(n)
min, maxO(log n)O(n)
sorted output (inorder)O(n)O(n)

Common mistakes#

Practice#

Practice exercise

Write kth_smallest(root, k) that returns the kth smallest value (1-based) in a BST without building the full sorted list.

Show hint

Do an iterative inorder traversal (go left, pop, visit, go right) and count visits. Stop when the count reaches k.

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

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

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

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print([kth_smallest(root, k) for k in range(1, 8)])
print(kth_smallest(root, 9))
Output
[20, 30, 40, 50, 60, 70, 80]
None

It stops after k visits, so it costs O(h + k) instead of O(n).

Key takeaway#

Next: keeping trees short automatically, in Balanced Trees (AVL).

Finished this lesson?

Related lessons

DSATrees and Binary Trees: Terminology and Python ImplementationLearn the tree data structure: root, parent, child, leaf, depth and height, binary trees and their types, building a binary tree in Python, and computing size, height and leaf count recursively.Intermediate9 min readDSATree Traversals: Preorder, Inorder, Postorder and Level OrderLearn binary tree traversals in Python: preorder, inorder and postorder (recursive and iterative with a stack), level-order traversal with a queue, and what each order is used for.Intermediate11 min readDSABalanced Binary Search Trees: AVL Trees and RotationsLearn how self-balancing BSTs stay fast: balance factors, left and right rotations, the four AVL imbalance cases, a working AVL insert in Python, and how red-black trees compare.Advanced11 min readDSABinary Search Explained: Iterative, Recursive and Boundary SearchesLearn binary search in Python: how halving gives O(log n), the iterative template, finding the first and last position of a value, the bisect module, and binary search on the answer.Intermediate10 min read