Binary Search Tree

Procedure SearchTree below is taken from program BinarySearchTree in the middle of the section on binary search trees in our recursion tutorial. (You may need to study/revise more of the recursion tutorial in order to understand the code).

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 code that calls the procedure is:

write('Word to search for? ');
readln(SearchItem);
Found := False;
SearchTree(RootPtr, LowerCase(SearchItem));
if not Found then
  writeln('Not found');

We explain the code by breaking it down into steps:

  1. The SearchTree code checks whether the root node is nil. If it is, there is an empty tree/subtree. A stopping condition is met while Found is still False and the output is 'Not found'.
  2. The code compares the search string with the string (Root^.Str) in the root node of the tree/subtree.
  3. If there is a match, the output is 'Found', the global variable Found becomes True, and a stopping condition is met.
  4. If the search string is less than Root^.Str, the next run of SearchTree follows the branch to the root of the left subtree. It then follows the same steps from 1 to 5 as necessary.
  5. If the search string is greater than Root^.Str, the next run of SearchTree follows the branch to the root of the right subtree. It then follows the same steps from 1 to 5 as necessary.

Searching using a BST is a form of binary searching and is efficient. If speed is of the utmost importance then the hash search in the next section is preferable.

Going Further

See also our Smart Pascal demonstration of searching a tree (not binary) by both breadth first search (BST) and depth first search (DFS).

Programming - a skill for life!

Linear search, binary search, binary search tree and hash search