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:
- 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'.
- The code compares the search string with the string (Root^.Str) in the root node of the tree/subtree.
- If there is a match, the output is 'Found', the global variable Found becomes True, and a stopping condition is met.
- 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.
- 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.
See also our Smart Pascal demonstration of searching a tree (not binary) by both breadth first search (BST) and depth first search (DFS).