search tree iterators the definition of the search tree adt specifies an iterator that can be used to traverse through the keys contained in the tree the implementation of the iterators for use with the linear list structures were rather simple for the sequence typeswe were able to initialize an index variable for accessing the elements that was incremented after each iteration of the for loop with linked listthe iterator can define and use an external reference that is initialized to the head node and then advanced through the list with each iteration of the loop traversals can be performed on binary search treebut this requires recursive solution we cannot easily advance to the next key without moving down into the tree and then backing up each time leaf is encountered one solution is to have the iterator build an array of elements by recursively traversing the treewhich we can then step through as the iterator progresses just as we did with the linear structures an iterator using this approach is provided in listing while this approach worksit requires the allocation of additional storage spacewhich can be significant if the tree contains large number of elements as an alternativewe can perform recursive traversal with the use of stack rememberrecursion simulates the use of stack without having to directly perform the push and pop operations any recursive function or method can be implemented using listing an iterator for the binary search tree using an array class _bstmapiterator def __init__selfrootsize )creates the array and fills it with the keys self _thekeys arraysize self _curitem keep track of the next location in the array self _bsttraversalroot self _curitem reset the current item index def __iter__self )return self returns the next key from the array of keys def __next__self )if self _curitem lenself _thekeys key self _thekeysself _curitem self _curitem + return key else raise stopiteration performs an inorder traversal used to build the array of keys def _bsttraversalselfsubtree )if subtree is not none self _bsttraversalsubtree left self _thekeysself _curitem subtree key self _curitem + self _bsttraversalsubtree right