listing partial implementation of the map adt using binary search tree class bstmap creates an empty map instance def __init__self )self _root none self _size returns the number of entries in the map def __len__self )return self _size returns an iterator for traversing the keys in the map def __iter__self )return _bstmapiteratorself _root storage class for the binary search tree nodes of the map class _bstmapnode def __init__selfkeyvalue )self key key self value value self left none self right none discussed throughout the section as with any binary treea reference to the root node must also be maintained for binary search tree the constructor defines the root field for this purpose and also defines the size field to keep track of the number of entries in the map the latter is needed by the len method the definition of the private storage class used to create the tree nodes is shown in lines - searching given binary search treeyou will eventually want to search the tree to determine if it contains given key or to locate specific element in the last we saw that there is single path from the root to every other node in tree if the binary search tree contains the target keythen there will be unique path from the root to the node containing that key the only question ishow do we know which path to takesince the root node provides the single access point into any binary treeour search must begin there the target value is compared to the key in the root node as illustrated in figure if the root contains the target valueour search is over with successful result but if the target is not in the rootwe must decide which of two possible paths to take from the definition of the binary search treewe know the key in the root node is larger than the keys in its left subtree and smaller than the keys in its right subtree thusif the target is less than the root' keywe move left and we move right if it' greater we repeat the comparison on the root node of the subtree and take the appropriate path this process is repeated until target is located or we encounter null child link