Tree Sort

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

Output from program DrawBST

A binary search tree has the following properties.
  • 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.

Programming - a skill for life!

Bubble sort, insertion sort, tree sort and quicksort