chap binary trees in the case when this node has two childrenthe depth of the node with smallest value in its right subtree thusin the worst casethe cost of any one of these operations is the depth of the deepest node in the tree this is why it is desirable to keep bsts balancedthat iswith least possible height if binary tree is balancedthen the height for tree of nodes is approximately log howeverif the tree is completely unbalancedfor example in the shape of linked listthen the height for tree of nodes can be as great as thusa balanced bst will in the average case have operations costing th(log )while badly unbalanced bst can have operations in the worst case costing th(nconsider the situation where we construct bst of nodes by inserting the nodes one at time if we are fortunate to have them arrive in an order that results in balanced tree ( "randomorder is likely to be good enough for this purpose)then each insertion will cost on average th(log )for total cost of th( log nhoweverif the nodes are inserted in order of increasing valuethen the resulting tree will be chain of height the cost of insertion in this case will be ni= iwhich is th( traversing bst costs th(nregardless of the shape of the tree each node is visited exactly onceand each child pointer is followed exactly once below is an example traversalnamed printhelp it performs an inorder traversal on the bst to print the node values in ascending order private void printhelp(bstnode rtif (rt =nullreturnprinthelp(rt left())printvisit(rt element())printhelp(rt right())while the bst is simple to implement and efficient when the tree is balancedthe possibility of its being unbalanced is serious liability there are techniques for organizing bst to guarantee good performance two examples are the avl tree and the splay tree of section other search trees are guaranteed to remain balancedsuch as the - tree of section heaps and priority queues there are many situationsboth in real life and in computing applicationswhere we wish to choose the next "most importantfrom collection of peopletasksor objects for exampledoctors in hospital emergency room often choose to see next the "most criticalpatient rather than the one who arrived first when scheduling programs for execution in multitasking operating systemat any given moment there might be several programs (usually called jobsready to run the