Binary Search Trees

A Binary Search Tree (BST) is a binary tree with the following additional property. The value at the root node is greater (or equal) than all the values in the left subtree. Likewise, the value is lesser than (or equal) all the values in the right subtree.

We keep things simple and don't consider the multiple equal values case. Rather, we implement dictionaries using binary trees.

A dictionary is a list of (key, value) pairs. A key can occur only once, that is, the key is unique. For example, we could use dictionaries to compute the count of words in a given text input.

The word count algorithm is simple:

words[] = split a string on space characters. 
for each word, search the dictionary if it is already present. 
if not in dictionary, insert (word, 1) 
if found in dictionary, take associated count, cnt 
update (word, cnt+1) 

The following figure shows an abstract dictionary on the left-hand side. The right-hand side of the diagram shows how we could realize it using a BST...