if is smaller than the value of the rootinsert into the left sub-tree if is larger than the value of the rootinsert into the right sub-tree if is equal to the value of the rootreport violated assumption thususing the primitive binary tree operatorswe have the procedureinsert( ,bstif isempty(bstreturn maketree(vemptytreeemptytreeelseif root(bstreturn maketree(root(bst)insert( ,left(bst))right(bst)elseif root(bstreturn maketree(root(bst)left(bst)insert( ,right(bst))else error('errorviolated assumption in procedure insert 'which inserts node with value into an existing binary search tree bst note that the node added is always leaf the resulting tree is once again binary search tree this can be proved rigorously via an inductive argument note that this procedure creates new tree out of given tree bst and new value vwith the new value inserted at the right position the original tree bst is not modifiedit is merely inspected howeverwhen the tree represents large databaseit would clearly be more efficient to modify the given treerather than to construct whole new tree that can easily be done by using pointerssimilar to the way we set up linked lists for the momentthoughwe shall not concern ourselves with such implementational details searching binary search tree searching binary search tree is not dissimilar to the process performed when inserting new item we simply have to compare the item being looked for with the rootand then keep 'pushingthe comparison down into the left or right subtree depending on the result of each root comparisonuntil match is found or leaf is reached algorithms can be expressed in many ways here is concise description in words of the search algorithm that we have just outlinedin order to search for value in binary search tree tproceed as follows if is emptythen does not occur in tand hence we stop with false otherwiseif is equal to the root of tthen does occur in tand hence we stop returning true ifon the other handv is smaller than the rootthenby definition of binary search treeit is enough to search the left sub-tree of hence replace by its left sub-tree and carry on in the same way similarlyif is bigger than the rootreplace by its right sub-tree and carry on in the same way notice that such description of an algorithm embodies both the steps that need to be carried out and the reason why this gives correct solution to the problem this way of describing algorithms is very common when we do not intend to run them on computer