(fig the sentinel may be considered as commonshared representative of all external nodes by which the original tree was extended (see fig )procedure locate (xintegertnode)nodebegin key : (*sentinel*while key do if key then : right else : left end endreturn end locate note that in this case locate(xtyields the value instead of nili the pointer to the sentinelif no key with value is found in the tree with root fig search tree with sentinel tree search and insertion the full power of the dynamic allocation technique with access through pointers is hardly displayed by those examples in which given set of data is builtand thereafter kept unchanged more suitable examples are those applications in which the structure of the tree itself variesi grows and/or shrinks during the execution of the program this is also the case in which other data representationssuch as the arrayfail and in which the tree with elements linked by pointers emerges as the most appropriate solution we shall first consider only the case of steadily growing but never shrinking tree typical example is the concordance problem which was already investigated in connection with linked lists it is now to be revisited in this problem sequence of words is givenand the number of occurrences of each word has to be determined this means thatstarting with an empty treeeach word is searched in the tree if it is foundits occurrence count is incrementedotherwise it is inserted as new word (with count initialized to we call the underlying task tree search with insertion the following data type definitions are assumedtype node pointer to record keycountintegerleftrightnode end finding the search path is again straightforward howeverif it leads to dead end ( to an empty subtree designated by pointer value nil)then the given word must be inserted in the tree at the place of