Binary Tree Search

We can efficiently search for a desired element of the tree by taking advantage of the ordering and using divide-and-conquer.

public static String search
                     (Tree start, String goal) {
    if ( start == null )
        return null;       // goal not found
     { int test = goal.compareTo(start.contents);
       if ( test == 0 )
          return start.contents;     // found
         else if ( test < 0 )
                 return search(start.left, goal);
            else return search(start.right, goal);
     } }

If the tree is balanced, the search takes only O(log(n)) time.

We return the contents because it is likely that the application will need to do something with it. For example, we might search on a customer name and retrieve the customer's account information.

Contents    Page-10    Prev    Next    Page+10    Index