sections binary search trees binary trees are data structure that impose an order on inserted nodesitems less than node are stored in the left subtreeand items greater than node are inserted in the right at the bottomthe subtrees are empty because of this structurebinary trees naturally support quickrecursive traversalsand hence fast lookup and search in wide variety of applications--at least ideallyevery time you follow link to subtreeyou divide the search space in half built-in options here toopython supports search operations with built-in tools dictionariesfor examplealready provide highly optimizedc-coded search table tool in factindexing dictionary by key directly is likely to be faster than searching python-coded equivalentx {empty dict for in [ ] [inone insert { none none none none nonefor in range( )print((ii in )end='lookup ( false( true( true( true( false( false( false( truebecause dictionaries are built into the languagethey are always available and will usually be faster than python-based data structure implementations built-in sets can often offer similar functionality--in factit' not too much of an abstraction to think of sets as valueless dictionariesx set(empty set for in [ ] add(iinsert { for in range( )print((ii in )end='lookup ( false( true( true( true( false( false( false( truein factthere are variety of ways to insert items into both sets and dictionariesboth are useful for checking if key is storedbut dictionaries further allow search keys to have associated valuesv [ { for in vset comprehension binary search trees