Binary Search Tree

Binary search tree (BST) is a binary tree. It provides some useful operations including search, insert, delete, minimum, maximum, successor and predecessor.

Binary Search Tree

A binary search tree must satisfy the following properties:

• Each node has a key, and the keys of any two nodes are not the same.
• All keys of the left subtree must be smaller than the key of the root.
• All keys of the right subtree must be larger than the key of the root.
• The left and right subtrees are also binary search trees.

The following are legal binary search trees.

Search

Suppose we want to search for x in a binary search tree, the algorithm is as follows. We list two algorithms, one uses recursive way and the other uses iterative way. Both approaches have the same time complexity , where h is the height of the tree.

Algorithm BSTSearch(root, x) {
    if root == null {
        return null
    } else if root.key == x {
        return root
    } else if root.key > x {
        return Search(root.left, x)
    } else {
        return Search(root.right, x)
    }
}

Algorithm BSTSearch(root, x) {
    node := root
    while node != null {
        if node.key == x {
            return node
        } else if node.key > x {
            node = node.left
        } else {
            node = node.right
        }
    }
    return null
}

Minimum and Maximum

In a binary search tree, to look for the minimum value, you just keep searching to the left, and you will find the minimum value. Conversely, to look for the maximum value, you just keep looking to the right, and you will find the maximum value. In the figure below, the minimum value is 3 on the most-left, and the maximum value is 48 on the most-right.

Algorithm BSTMinimum(node) {
    while node.left != null {
        node = node.left
    }
    return node
}

Algorithm BSTMaximum(node) {
    while node.right != null {
        node = node.right
    }
    return node
}

Successor and Predecessor

In the binary search tree, for any node x, its successor is the smallest key greater than x; its predecessor is the largest key smaller than x. In the figure below, the successor of 20 is 30, and the predecessor of 20 is 10.

Algorithm BSTSuccessor(node) {
    if node.right != null {
        return BSTMinimum(node.right)
    }
    p := node.parent
    while p != null && node == p.right {
        node := p
        p := p.parent
    }
    return p
}

Algorithm BSTMinimum(node) {
    if node.left != null {
        return BSTMaximum(node.left)
    }
    p := node.parent
    while p != null && node == p.left {
        node := p
        p := parent
    }
    return p
}

Insertion

Suppose we want to insert x in a binary search tree, the algorithm is as follows. First, we try to search for x, and if we find a node with key x, we cannot insert x because it already exists. If not found, we store the last node we searched in parent. If x is less than parent.key, insert x at parent.left. Otherwise, insert it into parent.right. The time complexity of insertion is , where h is the height of the tree.

Algorithm BSTInsertion(root, x) {
    node := root
    parent := root
    while node != null {
        parent := node
        if node.key == x {
            // found a node with key x
            return null
        } else if node.key > x {
            node = node.left
        } else {
            node = node.right
        }
    }

    q := TreeNode(x)
    q.left = q.right = null
    if root == null {
        return q
    } else {
        if parent.key > x {
            parent.left = q
        } else {
            parent.right = q
        }
        return root
    }
}

Deletion

Suppose we want to delete a node x in a binary search tree, we need to consider three cases.

The first is when x has no children, we just delete x directly. As shown in the figure below, we can delete 28 directly.

The second is when x has only a single child, we only need to connect the parent and child of x, and delete x. In the figure below, we connect 30 with 50 and delete 40.

The third is when x has two children, we need to find the successor z of x first. Then, remove z from the binary search tree. Finally, replace the key of x with the key of z. Since z is the successor of x, z must have no left subtree. So when deleting z, you will face the first or second case.

In the figure below, we want to delete 10. We first find the successor of 10, which is 12, and delete it. Then change the key of the node to be deleted to 12.

Algorithm BSTDelete(Tree, x) {
    if x.left == null || x.right == null {
        successor := x
    } else {
        successor := BSTSuccessor(x)
    }

    if successor.left != null {
        y := successor.left
    } else {
        y := successor.right
    }
    if y != null {
        y.parent := successor.parent
    }

    if successor.parent == null {
        Tree.root := y
    } else {
        if successor == successor.parent.left {
            successor.parent.left = y
        } else {
            successor.parent.right = y
        }
    }

    if successor != x {
        x.key = successor.key
    }
}

Time Complexity

Algorithm	Average	Worst Case
Search
Insert
Delete

Reference

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th Ed.
• Binary search tree, Wikipedia.