SEPARATE (Binary_Search_Trees_Generic)
FUNCTION Search (T: Tree; K : KeyType) RETURN Tree IS
------------------------------------------------------------------------
--| BST Search Operation, subunit of Binary_Search_Trees_Generic
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: January 1996                                     
------------------------------------------------------------------------
BEGIN -- Search

  IF T = NULL THEN         -- not in tree
    RAISE NotFound;
  ELSIF K < KeyOf(T.Info) THEN    -- search left subtree
    RETURN Search(T.Left, K);
  ELSIF KeyOf(T.Info) < K THEN    -- search right subtree
    RETURN Search(T.Right, K);
  ELSE                     -- found it!
    RETURN T;
  END IF;

END Search;