Question

Suppose that a Binary Search Tree is constructed by repeatedly inserting distinct values in to the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted in to the tree. 

Answer 1

Let us consider an element x to insert in a binary search tree. So for inserting the

element x first at level 0,then level 1 and suppose upto level (d-1). While examine at (d-1) level, x might have less or more in comaprison to element at (d-1). Then we insert x either left or right. In both cases no of examined code will be d. Now suppose we want to search for x, this time again traverses the same path as we traverse. While inserting the element, we stop at (d-1) the level but for searching we examine node at dth level also i.e. the node containing x. Thus number of node examine while inserting are d while incase of searching it is d+1 i.e. one more than while inserting, hence the result.