8.4BINARY SEARCH TREE

A Binary Search Tree (BST) is a variant of a binary tree. The special property of a binary search tree is that all the nodes in the left sub-tree have a value less than that of the root node. Similarly, all the nodes in the right sub-tree have a value more than that of the root node. Hence, the binary search tree is also known as an ordered binary tree, because all the nodes in a binary search tree are ordered. The left and the right sub-trees are also binary search trees, and thus the same property is applicable on every sub-tree in the binary search tree. Figure 8.14 represents a binary search tree in that all the keys are ordered.

In Figure 8.14, the root node is 50. The left sub-tree of the root node consists of the nodes 19, 7, 32, 25, and 43. We can see that all these nodes have smaller values than the root node, and hence it constitutes the left sub-tree. Similarly, the right sub-tree of the root node consists of the nodes 75, 87, 80, and 99. Here also,...