26 votes 26 votes A binary search tree is generated by inserting in order the following integers: $$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$ The number of nodes in the left subtree and right subtree of the root respectively is $(4, 7)$ $(7, 4)$ $(8, 3)$ $(3, 8)$ DS gate1996 data-structures binary-search-tree easy + – Kathleen asked Oct 9, 2014 edited Dec 17, 2023 by Hira Thakur Kathleen 30.5k views answer comment Share Follow See 1 comment See all 1 1 comment reply Abir Mazumder commented May 16, 2020 reply Follow Share Just jot down the sorted sequence . Since it's not a balanced binary tree , numbers in the sorted list smaller than the first element inserted i.e 50 in this case will be accommodated in left subtree and the rest will be accommodated in right subtree. 4 votes 4 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes Correct Option: B Root will be $50$. now insert one by one, greater to $50$ in the right sub tree, lesser in left sub tree. Or you can simply count the number looking at the i/p. less than $50$ are $7$. more than $50$ are $4$. Gate Keeda answered Oct 9, 2014 edited May 4, 2021 by soujanyareddy13 Gate Keeda comment Share Follow See all 2 Comments See all 2 2 Comments reply arpit_18 commented Jul 26, 2020 reply Follow Share How to know that root is 50? 1 votes 1 votes jayskhatri commented Mar 8, 2021 reply Follow Share @arpit_18 it is given in the question “inserting in order” so first digit in the sequence will be root. 1 votes 1 votes Please log in or register to add a comment.
9 votes 9 votes Here's how the BST looks like. For GATE, going with the >50 or <50 is preferable. Pronomita Dey 1 answered Jan 24, 2018 Pronomita Dey 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply Anoopsingh123 commented Dec 15, 2020 reply Follow Share If we write pre order for this the elements of bst comes in sorted order so 3 comes first and work as root, so just counting left of three and right of three we get the desired answer.. Correct me if i am wrong?? 0 votes 0 votes rhl commented Sep 20, 2021 reply Follow Share you are doing a pre-order traversal of a list of numbers. How did you do that? That is not possible. Pre-order, Post-order, and in-order traversal are defined on trees only. An in-order traversal of BST gives a sorted list if that is what you are referring to. 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 votes 50 is root Node in BST So greater than 50 will be in right subtree of 50 and less than 50 in left subtree So ans will be B(7,4) Anil Khatri answered Oct 17, 2016 Anil Khatri comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Since root will be 50, just count the number of elements less than or greater than 50. Shubhranshu answered May 25, 2020 Shubhranshu comment Share Follow See all 0 reply Please log in or register to add a comment.