trees binary search tree typicallyan avl tree is not usedinsteadtop-down red-black treeswhich are discussed in section are often used an important issue in implementing set and map is providing support for the iterator classes of courseinternallythe iterator maintains pointer to the "currentnode in the iteration the hard part is efficiently advancing to the next node there are several possible solutionssome of which are listed here when the iterator is constructedhave each iterator store as its data an array containing the set items this doesn' workit makes it impossible to efficiently implement any of the routines that return an iterator after modifying the setsuch as some of the versions of erase and insert have the iterator maintain stack storing nodes on the path to the current node with this informationone can deduce the next node in the iterationwhich is either the node in the current node' right subtree that contains the minimum item or the nearest ancestor that contains the current node in its left subtree this makes the iterator somewhat large and makes the iterator code clumsy have each node in the search tree store its parent in addition to the children the iterator is not as largebut there is now extra memory required in each nodeand the code to iterate is still clumsy have each node maintain extra linksone to the next smallerand one to the next larger node this takes spacebut the iteration is very simple to doand it is easy to maintain these links maintain the extra links only for nodes that have nullptr left or right links by using extra boolean variables to allow the routines to tell if left link is being used as standard binary search tree left link or link to the next smaller nodeand similarly for the right link (exercise this idea is called threaded tree and is used in many of the stl implementations an example that uses several maps many words are similar to other words for instanceby changing the first letterthe word wine can become dinefinelinemineninepineor vine by changing the third letterwine can become widewifewipeor wireamong others by changing the fourth letterwine can become windwingwinkor winsamong others this gives different words that can be obtained by changing only one letter in wine in factthere are over different wordssome more obscure we would like to write program to find all words that can be changed into at least other words by single one-character substitution we assume that we have dictionary consisting of approximately , different words of varying lengths most words are between and characters the distribution includes , six-letter words , seven-letter words , eight-letter words , nine-letter words , ten-letter wordsand , eleven-letter words (in realitythe most changeable words are three-four-and five-letter wordsbut the longer words are the time-consuming ones to check the most straightforward strategy is to use map in which the keys are words and the values are vectors containing the words that can be changed from the key with