We use the following procedure to search for a node with a predefined value in a binary search tree. Given a pointer to the root of the tree and a number,"value", FIND returns a pointer to a node with the same value if one exists. Otherwise, it returns NIL.

The procedure begins its search at the root and traces a path downward in the tree. For each node T encountered, it compares the value passed with T->value. If the two keys are equal, the search terminates. If T is smaller than value, the search continues in the left subtree of x, since the binary search tree property implies that k could not be stored in the right subtree. Symmetrically, if value is larger than T->value, the search continues in the right subtree. The node encountered during the recursion forms a path downward from the root of the tree.

FIND (T, value)
1. if (T = NIL) or (T->value = value)
2.     then return T
3. if (k < T->value)
4.     then return FIND(T->left, value)
5.     else  return FIND(T->right, value);

Previous Page
Return to Main Page