Skip to main content
Lesson 35 - Binary Tree Algorithms
Lesson MenuPreviousNext
  
Searching a Binary Tree page 6 of 8

  1. Searching an ordered binary tree can be solved iteratively or recursively. Here is the iterative version.

    TreeNode find(TreeNode root, Comparable valueToFind)
    {
      TreeNode node = root;
        
      while (node != null)
      {
        int result = valueToFind.compareTo(node.getValue());
        if (result == 0)
          return node;
        else if (result < 0)
          node = node.getLeft();
        else  // if (result > 0)
          node = node.getRight();
      }
      return null;
    }
  2. If the value is not in the tree, the node pointer will eventually hit a null.

  3. Notice the type of the argument, valueToFind, in the find method is designated as Comparable. This means that valueToFind belongs to a class that implements the library interface Comparable. find's code calls the compareTo method of the valueToFind object to determine the ordering relationship - that's why valueToFind must be a Comparable, not just an Object.

  4. A recursive version is left for you to solve as part of the lab exercise.

  5. The order of searching an ordered binary tree is O(log2N) for the best case situation. For a perfectly balanced tree, the capacity of each level is 2level #.

    Level #    Capacity of Level   Capacity of Tree
    
      0                1                  1
      1                2                  3
      2                4                  7
      3                8                 15
      4               16                 31
      5               32                 63
     etc...
  6. So starting at the root node, a tree of 63 nodes would require a maximum of 5 left or right moves to find a value. The number of steps in searching an ordered binary tree is approximately O(log2N).


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.