30 votes 30 votes Suppose that we have numbers between $1$ and $100$ in a binary search tree and want to search for the number $55$. Which of the following sequences CANNOT be the sequence of nodes examined? $\{10, 75, 64, 43, 60, 57, 55\}$ $\{90, 12, 68, 34, 62, 45, 55\}$ $\{9, 85, 47, 68, 43, 57, 55\}$ $\{79, 14, 72, 56, 16, 53, 55\}$ DS gateit-2006 data-structures binary-search-tree normal + – Ishrat Jahan asked Oct 31, 2014 • edited Dec 20, 2017 by kenzou Ishrat Jahan 18.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 49 votes 49 votes In option C search sequence progress in $...47,68,43,..$ At $47$ we see that search key $55$ is greater and it will be on right side of $47$. so in further comparison a value less than $47$ will not come Hence, option C is wrong. Sankaranarayanan P.N answered Nov 14, 2014 • edited Jun 13, 2018 by Milicevic3306 Sankaranarayanan P.N comment Share Follow See all 3 Comments See all 3 3 Comments reply Kapish Malik commented May 21, 2015 reply Follow Share Explanation: Search Key is 55. If Search key < element in sequence then we will consider left subtree and following elements in sequence must be smaller than that element and if search key > element in sequence then we will consider right subtree and following elements must be greater than left subtree. We will iterate till last element in sequence (i.e. till search key is found).For Example : search 55 and sequence is {10, 75, 64, 43, 60, 57, 55}. 55 > 10 then all elements in sequence following 10 are greater than 10. if yes continue if no then that cannot be sequence of node to be examined and break the loop. Continue loop till last element ie 55. Hope explanation makes sense and understandable. Hence C is correct ans. 10 votes 10 votes Sankaranarayanan P.N commented Nov 16, 2016 reply Follow Share in option C first compared element is 9. that is root. the required item is 55. so in a bst 55 >9 , so will be on the right subtree. now all the comparisons further will be on the right side . and all elements should be greater than 9. now . now next item is 85, it is <55 . so all elements following 85 will be less than 85 and greater than 9. and it will be on left side of 85. Next is 47. and 55 > 47 that means in order to search 55 we need to search in the right sub tree of 47. right sub tree of 47 will contain elements greater than 47 and less than 85( from previous step). we can see there is a 43 in the following sequence. Which is not possible because 43 < 47. If you progress all the other options in similar logic, you can see that they are all valid. you can try drawing the corresponding BST also hope this explanation is ok 12 votes 12 votes Prince Gupta commented Dec 22, 2016 reply Follow Share Thanks sir 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes Although @Sankaranarayanan P.N ji has provided good and quick way to solve this problem. But still mentioning two more ways to solve this problem. (1) In Method 1 we are solving problem via maintaining (Min, Max) window. (2) For getting some intuition about method 2. Please refer --> https://cs.stackexchange.com/questions/11043/number-of-possible-search-paths-when-searching-in-bst/11048#11048 . PS: Much explanation is not added because it will help readers in thinking something different :) Chhotu answered Oct 19, 2017 Chhotu comment Share Follow See all 0 reply Please log in or register to add a comment.
5 votes 5 votes it is similar to this question https://gateoverflow.in/2756/gate1996-4 Mudrakola Karthik 3 answered Jun 12, 2018 Mudrakola Karthik 3 comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes all answer looks correct but they have asked “sequence of nodes examined “ 43 in option C will come out of sequence as the validation fails Shakyaji answered Nov 25, 2021 Shakyaji comment Share Follow See all 0 reply Please log in or register to add a comment.