3 votes 3 votes The keys 1,2,3,.., n are inserted randomly into a binary search tree. What is the probability that subtree of root contains exactly n-2 keys ? A. 1/n2 B. 1/n C. 1/(n+1) D. (n-2)/n Probability probability engineering-mathematics + – gauravkc asked Jan 21, 2018 • reshown Jan 21, 2018 by gauravkc gauravkc 486 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments joshi_nitish commented Jan 21, 2018 reply Follow Share how ? 0 votes 0 votes srestha commented Jan 21, 2018 reply Follow Share n-2 elements in subtree of root So, root contain either 2 or (n-1) element So, there will 2 parts in BST [1 , 2] [3,4.................n] or [1,2............n-2][n-1,n] Now by catalin number we can find number of binary tree but no such formula for BST right? 0 votes 0 votes hacker16 commented Jan 21, 2018 reply Follow Share i think question is not complete. 0 votes 0 votes Please log in or register to add a comment.
