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. find’s code calls the compareTo method of the valueToFind object to determine the ordering relationship. We declare valueToFind as a Comparable, not just an Object to guarantee that it will have a compareTo method.
-
A recursive version is left for you to implement as part of Lab Assignment AB30.2, BS Tree continued.
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 #.
|
Capacity of Level
1
2
4
8
16
32
|
Capacity of Tree
1
3
7
15
31
63
|
-
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).
