binary search trees the number of trees which can be formed with given knots abg( ) - -" theorem on trees, cayley bsts are workhorse of data structures and can be used to solve almost every data structures problem reasonably efficiently they offer the ability to efficiently search for key as well as find the min and max elementslook for the successor or predecessor of search key (which itself need not be present in the bst)and enumerate the keys in range in sorted order bsts are similar to arrays in that the stored values (the "keys"are stored in sorted order howeverunlike with sorted arraykeys can be added to and deleted from bst efficiently specificallya bst is binary tree as defined in in which the nodes store keys that are comparablee integers or strings the keys stored at nodes have to respect the bst property--the key stored at node is greater than or equal to the keys stored at the nodes of its left subtree and less than or equal to the keys stored in the nodes of its right subtree figure on the next page shows bst whose keys are the first prime numbers key lookupinsertionand deletion take time proportional to the height of the treewhich can in worst-case be ( )if insertions and deletions are naively implemented howeverthere are implementations of insert and delete which guarantee that the tree has height (log nthese require storing and updating additional data at the tree nodes red-black trees are an example of height-balanced bsts and are widely used in data structure libraries common mistake with bsts is that an object that' present in bst is to updated the consequence is that lookup for that object returns falseeven though it' still in the bst as ruleavoid putting mutable objects in bst otherwisewhen mutable object that' in bst is to be updatedalways first remove it from the treethen update itthen add it back the bst prototype is as followsclass bstnode def __init__ (self data=none left=none right =none)self data self left self right data left right binary search trees boot camp searching is the single most fundamental application of bsts unlike hash tablea bst offers the ability to find the min and max elementsand find the next largest/next smallest element these operationsalong with lookupdelete and findtake time (log nfor library implementations of bsts both bsts and hash tables use (nspace--in practicea bst uses slightly more space