Sarthaks Test
0 votes
3.4k views
in Computer by (68.8k points)

Suppose that we have numbers between 1 and 1000 in a Binary Search Tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? Explain your answer. 

(i) 2, 252, 401, 398, 330, 344, 397, 363 

(ii) 924, 220, 911, 244, 898, 258, 362, 363 

(iii) 925, 202, 911, 240, 912, 245, 363 

(iv) 2, 399, 387, 219, 266, 382, 381, 278, 363 

(v) 935, 278, 347, 621, 299, 392, 358, 363 

1 Answer

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

(i) This is a valid representation of sequence. 

(ii) This is also a valid representation of sequence.

(iii)This could not be the sequence since 240 is encountered after 911 so it must be its left child, and any other node henceforth must be less than 911(parent). But the node 912 breaks this sequence, which is greater than 911 and lies on the left subtree of 911, which violates the basic rule of a Binary Search Tree.

(iv)This is also a valid representation of sequence. 

(v)This could not be a valid sequence since 621 is encountered after 347 so 621 must be its right child, and any other node henceforth must be greater than 347(parent). But this sequence is broken by the node 299 < 347 and lies on the right subtree of 347 which violates the basic rule of a Binary Search Tree.

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

...