binary search trees an important application of the inorder traversal algorithm arises when we store an ordered sequence of elements in binary treedefining structure we call binary search tree let be set whose unique elements have an order relation for examples could be set of integers binary search tree for is binary tree such thatfor each position of position stores an element of sdenoted as (pelements stored in the left subtree of (if anyare less than (pelements stored in the right subtree of (if anyare greater than (pan example of binary search tree is shown in figure the above properties assure that an inorder traversal of binary search tree visits the elements in nondecreasing order figure binary search tree storing integers the solid path is traversed when searching (successfullyfor the 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 starting at the root at each internal position encounteredwe compare our search value with the element (pstored 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 empty subtreethe 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 we illustrate several examples of the search operation in figure note that the running time of searching in binary search tree is proportional to the height of recall from proposition that the height of 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 is devoted to the study of search trees