A binary search tree is one method for implementing a keyed table. The advantage to this approach is that it combines the advantage of an array--the ability to do a binary search with the advantage of a linked list--its dynamic size. The efficiency of all of the operations is O(log n), only if the tree is reasonably height-balanced. Each operation involves examining at most one branch of the tree. In a balanced tree, the height of the tree is logarithmically related to the number of nodes.

There are three fundamental operations, find, insert, and delete. The find operation examines the value of the current node. If it matches the value being searched for, it stops. It goes left if the value being searched for is less than the value in the current node, and right if it is greater. If it reaches a leaf node, the value is not in the tree. As you watch the animation you will notice that the gray circle traces the path of the search.

The insert operation first performs a find operation. As you watch the animation, notice that the gray circle begins at the root and moves down the tree searching for the specified value. If it finds the value, no insertion is performed. If it does not find the value, it performs the insertion on the leaf node, where the search ended. Because of the bounded screen size, a node will not be added when the length of any branch reaches its maximum length.

Like the insert operation, the deletion also begins with a find operation. In this case, the operation fails if the value is not found. If found, there are three distinct cases: 1) the node to be deleted is a leaf node, 2) it has one child, 3) it has two children. The first case is the simplest. The node is simply removed from its branch of the tree. The second case is similar to deleting from a singly linked list. The node is removed and its parent is connected to its only child. Notice that in the animation the subtree is then moved up. This movement is not a part of the actual algorithm and is done to keep the tree looking uniform. The two child case is the most complicated. The node containing the value to be deleted is not removed. Instead, the value of the node containing its inorder successor is moved to that node and the former is deleted. Use the I'll Pick radio button to select the deletion value. In that way you will have control over what node is deleted.