Linked Data Structures - Java - page 828

EXAMPLE: (continued)
The methods in this class make extensive use of the recursive nature of binary trees. If
aNode is a reference to any node in the tree (including possibly the root node), then the
entire tree with root aNode can be decomposed into three parts:
1. The node aNode .
2. The left subtree with root node aNode.leftLink .
3. The right subtree with root node aNode.rightLink .
The left and right subtrees do themselves satisfy the Binary Search Tree Storage Rule, so
it is natural to use recursion to process the entire tree by doing the following:
1. Processing the left subtree with root node aNode.leftLink
2. Processing the node aNode
3. Processing the right subtree with root node aNode.rightLink
Note that we processed the root node after the left subtree (inorder traversal).
This guarantees that the numbers in the tree are output in the order smallest to
largest. The method showElementsInSubtree uses a very straightforward implemen-
tation of this technique.
Other methods are a bit more subtle in that only one of the two subtrees needs to be
processed. For example, consider the method isInSubtree , which returns true or false
depending on whether or not the parameter item is in the tree with root node
subTreeRoot . To see if the item is anyplace in the tree, you set subTreeRoot equal to the
root of the entire tree, as we did in the method contains . However, to express our recur-
sive algorithm for isInSubtree , we need to allow for the possibility of subtrees other
than the entire tree.
The algorithm for isInSubtree expressed in pseudocode is as follows:
if (The root node subTreeRoot is empty.)
return false ;
else if (The node subTreeRoot contains item.)
return true ;
else if (item < subTreeRoot.data)
return (The result of searching the tree with
root node subTreeRoot.leftLink);
return (The result of searching the tree with else //item > link.data
root node subTreeRoot.rightLink);
The reason this algorithm gives the correct result is that the tree satisfies the Binary
Search Tree Storage Rule, so we know that if
item < subTreeRoot.data