## Find

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