Suppose that we construct a binary search tree by repeatedly inserting distinct values into 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 into the tree.

Because inserting a value and searching for a value use the same methodology, we know that they both must examine at least the same number of nodes. Searching for a node will include one additional node: the node being searched for. Therefore, searching for a node will examine one more node than the amount examined when inserting a node.