One of the main benefits of a binary is that it stores data in such as way as it can be searched quickly and easily.

To search a binary tree, we start at the root node and compare it with the target value.  If the target is not the root node, we follow the left branch if the target is smaller, or the right branch if the target is bigger.  We then do the same for the next node.  Each time we follow a branch, we eliminate half of the tree (assuming the tree is balanced).

The code to search a tree is similar to that for building the tree.

Algorithm to search a binary tree

Start at the root node
REPEAT
    IF Target = current node THEN
        found = TRUE
    ELSE
        IF Target > current node THEN
            follow right pointer (handle right child with same algorithm)
        ELSE
            follow left pointer (handle left child with same algorithm)
        END IF
   END IF
UNTIL found = TRUE or null pointer encountered
 

Pseudocode to search a binary tree

The pseudocode to search a binary tree is shown below. In many ways it is similar to the code that created the tree. Make sure that you understand the principles of this program so that you recognise what it does if you see it again.

Notice that this procedure takes two parameters, root which is the node to search from (a value of 1 will search from the ultimate root of the tree) and Target which is what we are looking for.

A check is made to see if the target matches the current node (which is the root node for the first call). We then go on to check if the target is less than the current node (it could therefore be somewhere on the left branch). If so, and if this is not a terminal node (Left_Pointer[root] <> 0) , the procedure calls itself recursively but this time the root is the current node’s left pointer (a new sub-tree).

Sub Search(root As Integer, Target As String)

If Target  = Data[root] Then
    MsgBox "found at postion " & root
End If

'left hand sub-tree search
If Target  < Data[root] Then
    If Left_Pointer[root] <> 0 Then
        Call Search(Left_Pointer[root], Target)
    End If
End If

'Right hand sub-tree search
If Target  > Data[root] Then
    If Right_Pointer[root] <> 0 Then
        Call Search(Right_Pointer[root], Target)
    End If
End If

End Sub