Skip to content

Binary Search Tree#

A binary search tree (BST) is a binary tree where for every node: left subtree keys < node key < right subtree keys (or ≤ / ≥ depending on duplicate policy). In-order traversal yields sorted order.

When to use a BST#

Prefer BST Prefer hash table
Need sorted iteration Only exact lookup
Predecessor / successor No ordering needed
Range queries (with augmentation) O(1) average lookup suffices

Interview note: assume balanced BST for O(log n) unless problem creates a skewed tree. Self-balancing variants (AVL, red-black) restore balance after inserts — know they exist; rarely implement from scratch in Python interviews.

Complexity (n nodes, height h)#

Operation Balanced h ≈ log n Skewed h = n
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
In-order traversal O(n) O(n)
Space O(n) nodes + O(h) stack O(n)

Python: no built-in BST — use bisect on a sorted list, or implement nodes for the interview. Third-party SortedList is uncommon in live coding.

Validate BST (LC 98): each node must satisfy lo < node.val < hi for bounds passed from ancestors — comparing only immediate children is not enough.

BST example with search path

Implementation#

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

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

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

        self.root = _insert(self.root, key)

    def search(self, key):
        def _search(root, key):
            if root is None or root.key == key:
                return root
            if key < root.key:
                return _search(root.left, key)
            return _search(root.right, key)

        return _search(self.root, key) is not None

    def delete(self, key):
        def _delete(root, key):
            if root is None:
                return root
            if key < root.key:
                root.left = _delete(root.left, key)
            elif key > root.key:
                root.right = _delete(root.right, key)
            else:
                if root.left is None:
                    return root.right
                elif root.right is None:
                    return root.left
                min_larger_node = self._get_min(root.right)
                root.key = min_larger_node.key
                root.right = _delete(root.right, min_larger_node.key)
            return root

        self.root = _delete(self.root, key)

    def floor(self, key):
        def _floor(root, key, floor_val=None):
            if root is None:
                return floor_val
            if root.key == key:
                return root.key
            elif key < root.key:
                return _floor(root.left, key, floor_val)
            else:
                floor_val = root.key  # Current node could be a candidate for the floor
                return _floor(root.right, key, floor_val)

        return _floor(self.root, key)

    def ceil(self, key):
        def _ceil(root, key, ceil_val=None):
            if root is None:
                return ceil_val
            if root.key == key:
                return root.key
            elif key > root.key:
                return _ceil(root.right, key, ceil_val)
            else:
                ceil_val = root.key  # Current node could be a candidate for the ceil
                return _ceil(root.left, key, ceil_val)

        return _ceil(self.root, key)

    def inorder(self):
        def _inorder(root):
            return _inorder(root.left) + [root.key] + _inorder(root.right) if root else []

        return _inorder(self.root)

    def _get_min(self, root):
        while root.left:
            root = root.left
        return root

# Example usage:
bst = BinarySearchTree()
bst.insert(20)
bst.insert(8)
bst.insert(22)
bst.insert(4)
bst.insert(12)
bst.insert(10)
bst.insert(14)

# Inorder traversal
print("Inorder traversal:", bst.inorder())

# Search for an element
print("Search 10:", bst.search(10))  # Should return True
print("Search 25:", bst.search(25))  # Should return False

# Floor and Ceil
print("Floor of 13:", bst.floor(13))  # Should return 12
print("Ceil of 13:", bst.ceil(13))    # Should return 14

# Deleting a node
bst.delete(10)
print("Inorder after deleting 10:", bst.inorder())

bst.delete(8)
print("Inorder after deleting 8:", bst.inorder())