46 46 votes A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys. $81, 537, 102, 439, 285, 376, 305$ $52, 97, 121, 195, 242, 381, 472$ $142, 248, 520, 386, 345, 270, 307$ $550, 149, 507, 395, 463, 402, 270$ Which of the following statements is TRUE? I, II and IV are inorder sequences of three different BSTs I is a preorder sequence of some BST with $439$ as the root II is an inorder sequence of some BST where $121$ is the root and $52$ is a leaf IV is a postorder sequence of some BST with $149$ as the root Data Structures gateit-2008 data-structures binary-search-tree easy + – Ishrat Jahan 11.1k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Mitali gupta commented Oct 1, 2020 reply Follow flag I have one doubt. As option C is not true in all cases . Then if one of the option is NONE of these ..Then which one should be marked? 0 0 replyShare sauravgahlawat commented Jul 18, 2021 reply Follow flag option C says “inorder sequence of some BST” 2 2 replyShare AtharvP commented Jul 16, 2025 reply Follow flag There should instead of some BST all BST be there because inorder of bst is always in sorted order 0 0 replyShare Please log in or register to add a comment.
Best answer 49 49 votes Incorrect because I & IV are not in ascending order.(Inoder sequence of BST is in increasing order) I is a preorder sequence of some BST with $439$ as the root . False because if $439$ is root, it should be first element in preorder. This is correct. IV is a postorder sequence of some BST with $149$ as the root, False because if $149$ is root, it should be last element in postorder Akash Kanase answered Nov 23, 2015 • edited Dec 21, 2017 by kenzou Akash Kanase comment Share Follow See all 7 Comments 7 7 Comments reply Mahima Manik commented Jan 9, 2017 reply Follow flag A, B and D options are surely eliminated. But in C option, 52 is not necessarily the leaf node. 97 can be the right child if 52 and it will still give the same sequence. So C is not true in all the cases. 16 16 replyShare Gate Ranker18 commented Aug 20, 2017 reply Follow flag in options , instances are given so only consider these instance ya C is not true in all the cases. 1 1 replyShare nishitshah commented Oct 8, 2017 reply Follow flag @Mahima, you are true but in the question all the other options are incorrect and also the question says which of the following is true not "always true" 1 1 replyShare vishalshrm539 commented Aug 28, 2018 reply Follow flag @Mahima II is an inorder sequence of some BST where 121 is the root and 52 is a leaf some BST means there exists a BST with these properties. 2 2 replyShare Kiyoshi commented Apr 25, 2021 reply Follow flag those who are saying option C is not correct in all the cases…. II is an inorder sequence of some BST where 121 is the root and 52 is a leaf. 5 5 replyShare Vortex commented Sep 16, 2025 reply Follow flag I'm sure That C is the answer with all elements are in ascending order and 52 is the first element of inorder so it has to be the leaf ONLY. But what about the statemnt saying 121 as the root ! Are they saying as an assumption ? 0 0 replyShare vxi lin commented Oct 1, 2025 reply Follow flag Yes, @Vortex to my understanding of the question they do mean assume 121 as the root and 52 is a leaf will the inorder still be valid or not.. 0 0 replyShare Please log in or register to add a comment.
14 14 votes it should be C) Inorder sequences are sorted. In preorder traversal root comes first and in postorder traversal root comes last. Sneha Goel answered Nov 16, 2014 Sneha Goel comment Share Follow See all 2 Comments 2 2 Comments reply richa116 commented Dec 29, 2015 reply Follow flag pls justfy........."where 121 is the root and 52 is a leaf" 5 5 replyShare akankshadewangan24 commented Jun 20, 2017 reply Follow flag apply AVL rotation and do balance it you will got 52 at the end 1 1 replyShare Please log in or register to add a comment.
6 6 votes Answer should be option C Prateek Raghuvanshi answered Apr 2, 2018 Prateek Raghuvanshi comment Share Follow See 1 comment 1 1 comment reply mansi_003 commented Jul 12, 2023 reply Follow flag from where 142 and 52 coming explain? 0 0 replyShare Please log in or register to add a comment.
