## Introduction

The binary search tree is a binary tree with the following property.

Every node in the left subtree of a node x are less than or equal to x and every node in the right subtree are greater than or equal to x.

When I say node I mean the data (or key) of the node. This property is called a binary search property and the binary tree is, therefore, called a binary search tree. Figure 1 shows an example of a binary search tree.

If you look at any node in the figure, the nodes in the left subtree are less or equal to the node and the nodes in the right subtree are greater than or equal to the node. The height of a randomly generated binary search tree is O(log *n*). Due to this, on average, operations in binary search tree take only O(log *n*) time.

Some binary trees can have the height of one of the subtrees much larger than the other. In that case, the operations can take linear time. The examples of such binary trees are given in Figure 2.

But, on average, the height of the BST is O(log *n*).

In the next section, I explain the operations on BST in detail.

## Operations on BST

The summary of the operations I am going to discuss and their running times are outlined in the table below.

S. No. | Operation | Average Case | Worst Case |
---|---|---|---|

1 | Search | O(log n) | O(n) |

2 | Minimum | O(log n) | O(n) |

3 | Maximum | O(log n) | O(n) |

4 | Predecessor | O(log n) | O(n) |

5 | Successor | O(log n) | O(n) |

6 | Insert | O(log n) | O(n) |

7 | Delete | O(log n) | O(n) |

The working details of these operations are explained below.

### Search Operation

We can search a node with a given key (data) on a binary search tree. We start the process from the root node and move downward until we find the key we are searching for. If we find the node, the process terminates otherwise we return NIL. For each node `x`

we encounter, we compare the key `k`

with `x.key`

. If the two keys are equal, the search terminates. If `k`

is smaller than `x.key`

, the search continues in the left subtree of `x`

. Similarly, if `k`

is larger than `x.key`

, the search continues in the right subtree. Figure 3 illustrates this process with an example where we are searching for a node with key 25.

The recursive algorithm for the search operation is given below.

TREE-SEARCH(x, k)

ifx == NIL or k == x.key

returnx

ifk < x.key

returnTREE-SEARCH(x.left, k)

else returnTREE-SEARCH(x.right, k)

The running time of the search procedure is O(h) where h is the height of the tree.

### Minimum and Maximum

Given a binary search tree, we can find a node whose key is minimum by following the left child pointers from the root all the way down to the leaf node. Similarly, we can find the key whose key is maximum by following the right child pointers. In other words, the left-most node of a left subtree as the minimum key and the right-most node of a right subtree has the maximum key. Figure 4 illustrates this with an example tree.

An algorithm to find the node with minimum key is presented below.

TREE-MINIMUM(x)

whilex.left != NIL

x = x.left

returnx

The algorithm for the maximum is symmetric.

TREE-MAXIMUM(x)

whilex.right != NIL

x = x.right

returnx

The running time of `TREE-MINIMUM`

and `TREE-MAXIMUM`

is O(h) where h is the height of the tree.

### Successor and Predecessor

The successor of a node in a binary search tree is a node whose key is next key in the sorted order determined by an in-order walk. That means, if we sort the nodes based on the key in increasing order (in-order walk), each node is the successor of the preceding node. Similarly, each node is the predecessor of the following node. Due to the structure of the binary search tree, we can find the successor and predecessor of a node without comparing the keys.

To find the successor of a node `x`

with key `x.key`

, we do the following.

- If the right subtree of node
`x`

is non-empty, then the successor of`x`

is just the leftmost node in`x`

‘s right subtree. - If the right subtree of node
`x`

is empty and`x`

has a successor`y`

, then`y`

is the lowest ancestor of`x`

whose left child is also an ancestor of`x`

.

In a similar way, to find the predecessor of a node `x`

with key `x.key`

, we do the following.

- If the left subtree of node
`x`

is non-empty, then the successor of`x`

is just the rightmost node in`x`

‘s left subtree. - If the left subtree of node
`x`

is empty and`x`

has a successor`y`

, then`y`

is the lowest ancestor of`x`

whose right child is also an ancestor of`x`

.

The algorithm to find the successor `y`

of a node `x`

is given below.

TREE-SUCCESSOR(x)

ifx.right != NIL

returnTREE-MINIMUM(x.right)

y = x.parent

whiley != NIL and x == y.right

x = y

y = y.parentreturny

Similarly, the algorithm to find the predecessor `y`

of the node `x`

is

TREE-PREDECESSOR(x)

ifx.left != NIL

returnTREE-MAXIMUM(x.left)

y = x.parent

whiley != NIL and x == y.left

x = y

y = y.parentreturny

Both `TREE-SUCCESSOR`

and `TREE-PREDECESSOR`

take O(h) time to run.

### Insertion

The insertion operation inserts a node in the appropriate position so that the binary search tree property is not violated. To insert a node `z`

in the tree, we compare `z`

with node `x`

starting from the root node. If `z.key`

is smaller than `x.key`

, we continue the process in the left subtree otherwise we move to the right subtree. We continue this process until the value of `x`

is NIL. To make the process simple, we also need to keep track of the previous value `y`

of `x`

. When `x`

is NIL, we compare key of `y`

to the key of `z`

and make `z`

left or right child depending upon which one is larger. Figure 5 illustrates this process.

The algorithm for insertion operation is given below.

TREE-INSERT(z)

y = NIL

x = root

whilex != NIL

y = x

ifz.key < x.key

x = x.left

elsex = x.right

z.parent = y

ify == NIL

root = z

elseifz.key < y.key

y.left = z

elsey.right = z

The running time of this operation is O(h) since we travel down the tree following a simple path.

### Deletion

The deletion operation is a little bit tricky as we need to conserve the BST property after we delete the node. We may need to transform the tree in order to conserve the BST property. We need to handle three different cases in order to delete a node x. First two cases are simple and the last one is a little bit difficult.

**Case 1**: When x is a leaf node, we simply delete the node and change the x’s parent node’s left and right pointer accordingly.**Case 2**: When x has only one child (either left or right), we delete the node x and set the parent node’s left or right pointer to the x’s child node. Similarly, we adjust the parent pointer of x’s child node.**Case 3**: When x has both the children then we do the following.- We copy the minimum node y of x’s right subtree and place it in the place of x.
- Delete y. In deleting y, we need to handle either case 1 or case 2 depending upon whether y has one child or doesn’t have any children.

Let me explain the case 3 with the help of an example.

The algorithm for the deletion is given below.

TREE-DELETE(node, key)

ifnode == NIL

returnnode

elseifkey < node.key

node.left = TREE-DELETE(node.left, key)

elseifkey > node.key

node.right = TREE-DELETE(node.right, key)

else

//case 1

ifnode.left == NIL and node.right == NIL

deletenode

node = NIL

// case 2

elseifnode.left == NIL

temp = node

node = node.right

delete temp

elseifnode.right == NIL

temp = node

node = node->left

deletetemp

// case 3

else

temp = TREE-MINIMUM(node.right)

node.key = temp.key

node.right = TREE-DELETE(node.right, temp.key)

returnnode

The complexity of the deletion procedure is O(h).

## Tree Sort

One interesting application of binary search tree is in the tree sort. The in-order traversal of BST results into the sorted order of the keys. This is known as the tree sort and the complexity of this sort is O(nh).

## Implementation

The C++, Java, and Python implementations of the binary search tree is presented below.

1 | // Binary search tree implementation in C++ |

1 | // Binary search tree implementation in Java |

1 | # Binary search tree implementation in Java |