trees the search tree adt--binary search trees an important application of binary trees is their use in searching let us assume that each node in the tree stores an item in our exampleswe will assumefor simplicitythat these are integersalthough arbitrarily complex items are easily handled in +we will also assume that all the items are distinctand we will deal with duplicates later the property that makes binary tree into binary search tree is that for every nodexin the treethe values of all the items in its left subtree are smaller than the item in xand the values of all the items in its right subtree are larger than the item in notice that this implies that all the elements in the tree can be ordered in some consistent manner in figure the tree on the left is binary search treebut the tree on the right is not the tree on the right has node with item in the left subtree of node with item (which happens to be the rootwe now give brief descriptions of the operations that are usually performed on binary search trees note that because of the recursive definition of treesit is common to write these routines recursively because the average depth of binary search tree turns out to be (log )we generally do not need to worry about running out of stack space figure shows the interface for the binarysearchtree class template there are several things worth noticing searching is based on the operator that must be defined for the particular comparable type specificallyitem matches if both < and < are false this allows comparable to be complex type (such as an employee record)with comparison function defined on only part of the type (such as the social security number data member or salarysection illustrates the general technique of designing class that can be used as comparable an alternativedescribed in section is to allow function object the data member is pointer to the root nodethis pointer is nullptr for empty trees the public member functions use the general technique of calling private recursive functions an example of how this is done for containsinsertand remove is shown in figure figure two binary trees (only the left tree is search tree