Skip to content

Binary Search Tree (BST)

Idea Like You Are 10

A BST is a binary tree with a special rule:

  • left side has smaller values
  • right side has larger values

That rule makes searching faster.

Picture

1
2
3
4
5
        50
       /  \
     30    70
    / \   / \
   20 40 60 80

1
2
3
4
5
6
7
search(root, key):
    if root == NULL or root.data == key:
        return root
    if key < root.data:
        return search(root.left, key)
    else:
        return search(root.right, key)

Insert

1
2
3
4
5
6
7
8
insert(root, key):
    if root == NULL:
        return new node(key)
    if key < root.data:
        root.left = insert(root.left, key)
    else if key > root.data:
        root.right = insert(root.right, key)
    return root

Delete

Three cases:

  1. node is a leaf
  2. node has one child
  3. node has two children

For case 3, replace with inorder successor or predecessor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
delete(root, key):
    if root == NULL:
        return NULL

    if key < root.data:
        root.left = delete(root.left, key)
    else if key > root.data:
        root.right = delete(root.right, key)
    else:
        if root.left == NULL:
            return root.right
        if root.right == NULL:
            return root.left

        temp = minimum(root.right)
        root.data = temp.data
        root.right = delete(root.right, temp.data)
    return root

Traversal

Inorder traversal of BST gives sorted order.

Complexity Analysis

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

Why?

  • if the tree stays balanced, height is about log n
  • if it becomes skewed like a chain, height becomes n

Example of bad case:

1
10 -> 20 -> 30 -> 40

That is why self-balancing trees are useful.