# 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? ');
Found := False;
SearchTree(RootPtr, LowerCase(SearchItem));

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