The initial formation of a binary search tree (BST) from an unordered list is a form of insertion sort; as you build the tree, each version of the tree is completely sorted and you insert the next item into its correct position immediately.
We follow the usual practice of covering the BST separately because the code for a tree is quite different and more difficult. We have covered the BST in a section of our tutorial on recursion. The output from a demonstration program is reproduced here:
Output from program DrawBST
- The left subtree of a given node contains only nodes with values less than that of the given node. (E and F are less than K. E, F, K and L are less than M.)
- The right subtree of a given node contains only nodes with values greater than that of the given node (F > E, L > K and Q > M).
- Both the left and right subtrees must also be binary search trees.
Generally, the information represented by each node is a record rather than a single value, and you compare the keys of nodes when you position each record and when you search for a record. In program BinarySearchTree, each record comprises a left and right pointer with a string Str as the key. The SearchTree procedure is recursive and homes in efficiently on the target.
Procedure SearchTree (below) examines the root node first. If the root is nil, the target does not exist in the tree. Otherwise, if the target equals Str in the root, the search is successful. If the target is less than Str in the root, SearchTree calls itself to search the left subtree. If it is greater, SearchTree calls itself to search the right subtree. This process is repeated until the target is found or the subtree is nil. If the target is not found before a nil subtree is reached, then it must be absent.
procedure SearchTree(Root: NodePtr; Target: string); begin if Root <> nil then begin if Root^.Str = Target then begin writeln('Found'); Found := True; end else if Target < Root^.Str then SearchTree(Root^.Left, Target) else SearchTree(Root^.Right, Target); end; end;
The use of a BST for the combination of sorting and searching is “warmly recommended” by Knuth.