trees fig the final binarysearchtree object contents then the values in the right subtree are yielded by writing for elem in self right the result of this recursive function is an inorder traversal of the tree binary search trees are of some academic interest howeverthey are not used much in practice in the average caseinserting into binary search tree takes (log ntime to insert items into binary search tree would take ( log ntime soin the average case we have an algorithm for sorting sequence of ordered items howeverit takes more space than list and the quicksort algorithm can sort list with the same big-oh complexity in the worst casebinary search trees suffer from the same problem that quicksort suffers from when the items are already sortedboth quicksort and binary search trees perform poorly the complexity of inserting items into binary search tree becomes ( in the worst case the tree becomes stick if the values are already sorted and essentially becomes linked list there are couple of nice properties of binary search trees that random access list does not have inserting into tree can be done in (log ntime in the average case while inserting into list would take (ntime deleting from binary search tree can also be done in (log ntime in the average case looking up value in binary search tree can also be done in (log ntime in the average case if we have lots of insertdeleteand lookup operations for some algorithma tree-like structure may be useful butbinary search trees cannot guarantee the (log ncomplexity it turns out that there are implementations of search tree structures that can guarantee (log ncomplexity or better for insertingdeletingand searching for values few examples are splay treesavl-treesand -trees which are all studied later in this text search spaces sometimes we have problem that may consist of many different states we may want to find particular state of the problem which we'll call the goal consider sudoku puzzles sudoku puzzle has statereflecting how much of it we have this copy belongs to 'acha