Sarthaks Test
0 votes
78 views
in Computer by (69.3k points)

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. 

1 Answer

+1 vote
by (68.8k points)
selected by
 
Best answer

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. 

Related questions

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...