Chapter 8, Problem 31CRP

Design a nonrecursive algorithm to replace the recursive one represented in Figure 8.21.

def Search(Tree, TargetValue):

if (Tree is None):

return None # Search failed

elif (TargetValue = = Tree.Value):

return Tree # Search succeeded

elif (TargetValue < Tree.Value):

return Search(Tree.Left, TargetValue)

# Apply the function Search to see if TargetValue is in the subtree identified by the root's left child pointer, and report the result of that search.

elif (TargetValue > Tree.Value):

return Search(Tree.Right, TargetValue)

# Apply the function Search to see if TargetValue is in the subtree identified by the ‘ right child pointer, and report the result of that search.

Figure 8.21

The binary search as it would appear if the list were implemented as a linked binary tree