search trees method in searching for target keythe function starts at the root node and works its way down into the tree until either the key is located or null link is encountered the worst case time for the search operation depends on the number of nodes that have to be examined in the previous we saw that the worst case time of tree traversal was linear since it visited every node in the tree when null child link is encounteredthe tree traversal backtracks to follow the other branches during searchhoweverthe function never backtracksit only moves down the treefollowing one branch or the other at each node note that the recursive function does unwind in order to return to the location in the program where it was first invokedbut during the unwinding other branches are not examined the search follows single path from the root down to the target node or to the node at which the search falls off the tree the worst case occurs when the longest path in the tree is followed in search of the target and the longest path is based on the height of the tree binary trees come in many shapes and sizes and their heights can vary butas we saw in the previous tree of size can have minimum height of roughly log when the tree is complete and maximum height of when there is one node per level if we have no knowledge about the shape of the tree and its heightwe have to assume the worst and in this case that would be tree of height thusthe time required to find key in binary search tree is (nin the worst case searching for the minimum key in binary search tree is also linear time operation even though it does not compare keysit does have to navigate through the tree by always taking the left branch starting from the root in the worst casethere will be one node per level with each node linked to its parent via the left child link the bstinsert(methodwhich implements the algorithm for inserting new element into the treeperforms search to find where the new key belongs in the tree we know from our earlier analysis the search operation requires linear time in the worst case how much work is done after locating the parent of the node that will contain the new elementthe only work done is the creation of new node and returning its link to the parentwhich can be done in constant time thusthe insertion operation requires (ntime in the worst case the bstremove(method also requires (ntimethe analysis of which is left as an exercise operation worst case bstsearch(rootko(nbstminimum(rooto(nbstinsert(rootko(nbstdelete(rootko(ntraversal (ntable time-complexities for the binary search tree operations