trees template class binarysearchtree public/same methodswith object replacing comparable privatebinarynode *rootcomparator islessthan/same methodswith object replacing comparable /*internal method to test if an item is in subtree is item to search for is the node that roots the subtree *bool containsconst object xbinarynode * const ift =nullptr return falseelse ifislessthanxt->element return containsxt->left )else ifislessthant->elementx return containsxt->right )else return true/match }figure illustrates use of function object to implement binary search tree insert the insertion routine is conceptually simple to insert into tree tproceed down the tree as you would with contains if is founddo nothing otherwiseinsert at the last spot on the path traversed figure shows what happens to insert we traverse the tree as though contains were occurring at the node with item we need to go rightbut there is no subtreeso is not in the treeand this is the correct spot to place duplicates can be handled by keeping an extra field in the node record indicating the frequency of occurrence this adds some extra space to the entire tree but is better than putting duplicates in the tree (which tends to make the tree very deepof course