Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
+1 vote
72.4k views
in Computer by (69.2k points)
closed by

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 

2 Answers

+1 vote
by (69.7k 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.

+1 vote
by (17.0k points)

(i) Sequence is valid.

(ii) Sequence is valid.

(iii) In step 3 we go from 911 to 240 which means we take the left path. In the very next step we hit 912 which cannot be contained in a left subtree of the 911 node.

(iv) Sequence is valid.

(v) After taking the right path from 347 we encounter the value 299 which cannot be contained in a right subtree of the 347 node.

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

...