binary search trees all of the structures we discuss in this are search treesthat istree data structures that can be used to implement dictionary let usthereforebegin by briefly reviewing the fundamental methods of the dictionary adtfind( )return an entry with key kif it exists findall( )return an iterable collection of all entries with keys equal to insert( , )insert an entry with key and value remove( )remove an entry eand return it removeall( )remove all entries with key kreturning an iterator of their values method find returns null if is not found the ordered dictionary adt includes some additional methods for searching through predecessors and successors of key or entrybut their performance is similar to that of find so we will be focusing on find as the primary search operation in this binary trees are an excellent data structure for storing the entries of dictionaryassuming we have an order relation defined on the keys as mentioned previously (section ) binary search tree is binary tree such that each internal node of stores an entry ( ,xsuch thatkeys stored at nodes in the left subtree of are less than or equal to keys stored at nodes in the right subtree of are greater than or equal to as we show belowthe keys stored at the nodes of provide way of performing search by making comparison at each internal node vwhich can stop at or continue at ' left or right child thuswe take the view here that binary search trees are nonempty proper binary trees that iswe store entries only at the internal nodes of binary search treeand the external nodes serve only as "placeholders this approach simplifies several of our search and update algorithms incidentallywe could have allowed for improper binary search treeswhich have better space usagebut at the expense of more complicated search and update methods independent of whether we view binary search trees as proper or notthe important property of binary search tree is the realization of an ordered dictionary (or mapthat isa binary search tree should hierarchically represent an ordering of its keysusing relationships between parent and children specificallyan inorder traversal (section of the nodes of binary search tree should visit the keys in nondecreasing order