Binary Search Tree (BST)

After this topic

You will be able to explain the core rules of a Binary Search Tree, implement insertion and search in code, and obtain sorted data using an in-order traversal.

Limitations of Arrays

Binary search in a sorted array is fast, at O(log n). However, insertion and deletion are slow – you have to shift the rest of the elements to make space:

text

[2, 5, 8, 12, 15]
     ↑ insert 7 here
[2, 5, 7, 8, 12, 15]  ← 8, 12, and 15 must be shifted to the right (O(n))

We need a data structure that is fast for both searching and inserting. This is where the Binary Search Tree comes in.

The Core Rule

A Binary Search Tree (BST) follows only one rule:

Left child < Parent < Right child

text

8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

For any node, all values in its left subtree are less than it, and all values in its right subtree are greater than it.

Node Implementation

python

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

Each node has one value and two pointers to its left and right children.

Insertion

When inserting a new value, start at the root and go down according to the rule:

python

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

python

# Create the tree
root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)

If the value is less than the current node, go left; if it is greater, go right. When you find an empty spot, create a new node there.

Search

python

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

python

print(search(root, 7))   # True
print(search(root, 5))   # False

It works the same way as binary search. At each step, you eliminate half of the tree, so it is O(log n) for a balanced tree.

Search process (searching for 7):

text

8 → 7 < 8, go left
3 → 7 > 3, go right
6 → 7 > 6, go right
7 → Found it!

In-order Traversal – Sorted Output

If you visit the tree in the order "left → self → right", you get the values in sorted order. This is called an in-order traversal.

python

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

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

Following the BST rule (left < parent < right), visiting from the left naturally results in ascending order. You get sorted data without a separate sorting algorithm.

Three Traversals

python

def preorder(root):   # Pre-order: self → left → right
    if root is None: return []
    return [root.value] + preorder(root.left) + preorder(root.right)

def postorder(root):  # Post-order: left → right → self
    if root is None: return []
    return postorder(root.left) + postorder(root.right) + [root.value]

python

print(preorder(root))   # [8, 3, 1, 6, 4, 7, 10, 14, 13]
print(inorder(root))    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(postorder(root))  # [1, 4, 7, 6, 3, 13, 14, 10, 8]

Traversal	Order	Use Case
Pre-order	Self → Left → Right	Tree copy, serialization
In-order	Left → Self → Right	Sorted output
Post-order	Left → Right → Self	Tree deletion, expression tree evaluation

Worst Case

The performance of a BST depends on the balance of the tree:

text

# Balanced tree (O(log n))     # Skewed tree (O(n)) — basically a linked list
        8                    1
       / \                    \
      3   10                   2
     / \    \                   \
    1   6    14                  3
                                  \
                                   4

Inserting sorted data in order results in a skewed tree. To solve this, there are self-balancing trees like AVL trees and Red-Black trees. Python's sorted(), Java's TreeMap use these balanced trees internally.

Time Complexity Summary

Operation	Average	Worst (Skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)

BST Deletion – Three Cases

Deletion is the most complex operation in a BST:

python

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:
        # Case 1: No children (leaf) – just delete
        if root.left is None and root.right is None:
            return None
        # Case 2: One child – the child replaces the node
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Case 3: Two children – replace with in-order successor
        else:
            successor = find_min(root.right)
            root.value = successor.value
            root.right = delete(root.right, successor.value)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

When deleting a node with two children, replace it with the minimum value in its right subtree (in-order successor). This maintains the sorted property of the BST.

Do we use BST directly in practice?

Python does not have a built-in BST module. Instead:

python

from bisect import insort, bisect_left

sorted_list = []
insort(sorted_list, 5)   # Insert while maintaining order
insort(sorted_list, 3)
insort(sorted_list, 7)
print(sorted_list)  # [3, 5, 7]

idx = bisect_left(sorted_list, 5)  # Binary search
print(sorted_list[idx])  # 5

The bisect module provides O(log n) search similar to a BST in a sorted list. Insertion is O(n) (array shifting), so use a third-party library like SortedContainers if insertions are frequent.

BST vs. Hash Table vs. Sorted Array

Operation	BST (Balanced)	Hash Table	Sorted Array
Search	O(log n)	O(1) average	O(log n)
Insert	O(log n)	O(1) average	O(n)
Delete	O(log n)	O(1) average	O(n)
Min/Max	O(log n)	O(n)	O(1)
Range Search	O(log n + k)	O(n)	O(log n + k)
Sorted Output	O(n)	O(n log n)	O(n)

Hash tables are faster, but BSTs are better when you need "ordered data". Database indexes that need to query for "values between 100 and 200" are a good example.

BST is suitable when you need to "maintain sorted data dynamically". It is a data structure that combines the advantages of arrays and linked lists.

BioPlayground

Binary Search Tree (BST)

Binary Search Tree (BST)

After this topic

Limitations of Arrays

The Core Rule

Node Implementation

Insertion

Search

In-order Traversal – Sorted Output

Three Traversals

Worst Case

Time Complexity Summary

BST Deletion – Three Cases

Do we use BST directly in practice?

BST vs. Hash Table vs. Sorted Array

💬 Questions & Comments