179 views
2 votes
2 votes
Which of the following is not a valid sequence of key traversals while searching the key $44$ in a binary search tree?
  1. $11,88,22,77,33,66,44$
  2. $11,22,33,44$
  3. $88,11,22,77,55,44$
  4. $66,11,22,77,33,44$

1 Answer

Best answer
5 votes
5 votes
While searching in a binary search tree, if a value smaller than the key is found, then all the following keys will be larger than this smaller value. Similarly, if a value larger than the key is found, all the following keys will be smaller than this larger value. Here, options $A,B$ and $C$ are valid key sequences but option D is not as here, we first encounter $66$ which is larger than the search key $44,$ and after this $77 > 66$ is given which is not possible in a binary search.
selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Aug 9, 2020
278 views
The data structures most suitable to do an inorder and level order traversals of a binary tree respectively areStack and QueueQueue and StackStack and StackQueue and Queu...
3 votes
3 votes
1 answer
3
gatecse asked Aug 9, 2020
227 views
The cut vertices in the given graph areE and FA, C and DC, E and FB and C
1 votes
1 votes
1 answer
4