Recall that a binary tree is a rooted tree wherein no node has more than two children. Additionally, every child is either a left child or a right child of its parent, even if it is its parent’s only child. In the most popular binary tree representation, each tree node has three pointers: a parent pointer, a left pointer and a right pointer. Each node also stores a key (its value).

In a binary search tree, elements are maintained in a (somewhat) sorted order.

A binary search tree satisfies the binary-search-tree property (also called the binary-search-tree invariant):

When a node has only one child, that child is either a left child or a right child, depending on whether its key is smaller or larger than its parent’s key. A key equal to the parent’s key can go into either subtree.

Below is an example of a binary search tree.

       18
      /  \
    12    25
   / \    / \
  4  15  25  30
 /  /  \    /
1  13  17  28
 \  \       \
  3  14      29

An in-order traversal of a binary search tree visits the nodes in sorted order. In this sense, a search tree maintains a sorted list of its elements.

Operations on a search tree are usually more efficient than the same operations on a sorted linked list.

The insert method inserts a new node into the tree.

We start by following the same path through the tree as find. When we reaches a null pointer (missing node), replace that node with a new node storing the new key.

Duplicate keys are allowed. If insert finds a node that already has the same key, we’ll put the new node in the right subtree of the older one. (We could just as easily choose the left subtree; it doesn’t matter.)

Pseudocode:

insert(tree, newKey):
    newNode = Node()
    newNode.left = newNode.right = nil
    newNode.key = newKey

    nodeToCheck = tree.root
    parentOfNewNode = nil
    while nodeToCheck ≠ nil:
        parentOfNewNode = nodeToCheck
        if newNode.key < nodeToCheck.key:
            nodeToCheck = nodeToCheck.left
        else:
            nodeToCheck = nodeToCheck.right
    newNode.parent = parentOfNewNode
    if parentOfNewNode == nil:
        // tree was empty
        tree.root = newNode
    else if newNode.key < parentOfNewNode.key:
        parentOfNewNode.left = newNode
    else:
        parentOfNewNode.right = newNode

The remove method removes a node with the specified key from the tree. If there are multiple nodes with that key, we remove only one node (the first one that we happen to find).

We start by following the same path through the tree as find. If the key is not in the tree, we are done. Otherwise, let n be the first node with that key.

If n has two children, however, we have to be a bit more clever. Let successorNode be the node in n's right subtree with the smallest key. We detach successorNode from its parent and replace replace n with successorNode in the tree. Since successorNode's key is the next smallest key after the key we wanted to remove, the binary-search-tree property still holds.

In order to move subtrees around within the binary search tree, we’ll define a subroutine transplant, which replaces one subtree as a child of its parent with another subtree:

transplant(tree, oldChild, newChild):
    if oldChild.parent == nil:
        tree.root = newChild
    else if oldChild == oldChild.parent.left:
        oldChild.parent.left = newChild
    else:
        oldChild.parent.right = newChild
    if newChild ≠ nil:
        newChild.parent = oldChild.parent

remove(tree, key):
    nodeToRemove = find(key)
    if nodeToRemove ≠ nil:
        if nodeToRemove.left == nil:
            transplant(tree, nodeToRemove, nodeToRemove.right)
        else if nodeToRemove.right == nil:
            transplant(tree, nodeToRemove, nodeToRemove.left)
        else:
            successorNode = minimum(nodeToRemove.right)
            if successorNode.parent ≠ nodeToRemove:
                // detach successorNode from its parent
                transplant(tree, successorNode, successorNode.right)
                successorNode.right = nodeToRemove.right
                successorNode.right.parent = successorNode
            // replace nodeToRemove with successorNode
            transplant(tree, nodeToRemove, successorNode)
            successorNode.left = nodeToRemove.left
            successorNode.left.parent = successorNode

The successor of a node $x$ is the node with the smallest key $< x.key$ if all keys are distinct and $\leq x.key$ if duplicate keys are allowed.

The predecessor of a node $x$ is the node with the smallest key $> x.key$ if all keys are distinct and $\geq x.key$ if duplicate keys are allowed.

As you can see, the structure of a binary search tree allows us to determine the successor and the predecessor of a node without ever comparing keys.

Running times of find, insert and remove are $O(h)$ where $h$ is the height of the tree.

In the worst case, the height of the tree is $\Theta(n)$ where $n$ is the number of nodes in the tree.

1
 \
  2
   \
    3
     \
      4
       \
        5

In a perfectly balanced binary tree with height $h$, the number of nodes $n = 2^{h + 1} - 1$. In other words, no node has depth $d > \log_2 n$.

Therefore, the running times of find, insert and remove are $O(\log n)$ where $n$ is the number of nodes in the tree.

In a balanced BST, all the leaf nodes are at the same level.

A balanced BST stays balanced when we insert new elements and remove the existing ones.

Some of the popular data structures that implement self-balancing BSTs include: