the blue solid path is traversed when searching (successfullyfor the blue dashed path is traversed when searching (unsuccessfullyfor we can use binary search tree for set to find whether given search value is in sby traversing path down the tree tstarting at the root (see figure at each internal node encounteredwe compare our search value with the element (vstored at if ( )then the search continues in the left subtree of if ( )then the search terminates successfully if > ( )then the search continues in the right subtree of finallyif we reach an external nodethe search terminates unsuccessfully in other wordsa binary search tree can be viewed as binary decision tree (recall example )where the question asked at each internal node is whether the element at that node is less thanequal toor larger than the element being searched for indeedit is exactly this correspondence to binary decision tree that motivates restricting binary search trees to be proper binary trees (with "place-holderexternal nodesnote that the running time of searching in binary search tree is proportional to the height of recall from proposition that the height of proper binary tree with nodes can be as small as log( or as large as ( )/ thusbinary search trees are most efficient when they have small height we illustrate an example search operation in binary search tree in figure and we study binary search trees in more detail in section using inorder traversal for tree drawing