analysis of binary tree searching the analysis of the worst-case running time of searching in binary search tree is simple algorithm treesearch is recursive and executes constant number of primitive operations for each recursive call each recursive call of treesearch is made on child of the previous position that istreesearch is called on the positions of path of that starts at the root and goes down one level at time thusthe number of such positions is bounded by where is the height of in other wordssince we spend ( time per position encountered in the searchthe overall search runs in (htimewhere is the height of the binary search tree (see figure time per level ( height tree to( ( total timeo(hfigure illustrating the running time of searching in binary search tree the figure uses standard caricature of binary search tree as big triangle and path from the root as zig-zag line in the context of the sorted map adtthe search will be used as subroutine for implementing the getitem methodas well as for the setitem and delitem methodssince each of these begins by trying to locate an existing item with given key to implement sorted map operations such as find lt and find gtwe will combine this search with traversal methods before and after all of these operations will run in worst-case (htime for tree with height we can use variation of this technique to implement the find range method in time ( )where is the number of items reported (see exercise - admittedlythe height of can be as large as the number of entriesnbut we expect that it is usually much smaller indeedlater in this we show various strategies to maintain an upper bound of (log non the height of search tree