37 votes 37 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 DS gateit-2008 data-structures binary-search-tree easy + – Ishrat Jahan asked Oct 29, 2014 edited Dec 21, 2017 by kenzou Ishrat Jahan 6.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Mitali gupta commented Oct 1, 2020 reply Follow Share 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 votes 0 votes sauravgahlawat commented Jul 18, 2021 reply Follow Share option C says “inorder sequence of some BST” 2 votes 2 votes Please log in or register to add a comment.
Best answer 39 votes 39 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 5 Comments See all 5 5 Comments reply Show 2 previous comments nishitshah commented Oct 8, 2017 reply Follow Share @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 votes 1 votes vishalshrm539 commented Aug 28, 2018 reply Follow Share @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 votes 2 votes Kiyoshi commented Apr 25, 2021 reply Follow Share 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. 2 votes 2 votes Please log in or register to add a comment.
14 votes 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 See all 2 2 Comments reply richa116 commented Dec 29, 2015 reply Follow Share pls justfy........."where 121 is the root and 52 is a leaf" 3 votes 3 votes akankshadewangan24 commented Jun 20, 2017 reply Follow Share apply AVL rotation and do balance it you will got 52 at the end 1 votes 1 votes Please log in or register to add a comment.
4 votes 4 votes Answer should be option C Prateek Raghuvanshi answered Apr 2, 2018 Prateek Raghuvanshi comment Share Follow See 1 comment See all 1 1 comment reply mansi_003 commented Jul 12, 2023 reply Follow Share from where 142 and 52 coming explain? 0 votes 0 votes Please log in or register to add a comment.