| |
Searching a Binary Tree | page 6 of 8 |
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;
}
If the value is not in the tree, the node pointer will eventually hit a null .
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 .
A recursive version is left for you to solve as part of the lab exercise.
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...
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).
|