0 votes 0 votes The number of distinct BSTs that can be drawn having the same inorder traversal of tree as 6,12,20,32,45 are........ mystylecse asked Sep 23, 2017 mystylecse 257 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes The following observations to be kept in mind : a) If keys are same , then we will get the same inorder traversal for different BSTs.. b) If a tree having some root 'r' is a BST , then the subtrees of its left and right child will also be BSTs provided the subtree is non empty.. c) No of BSTs with 'k' different keys = kth Catalan number = C(2k,k) / (k+1) So here we have 5 distinct keys.. Hence number of BSTs : C(10,5 ) / 6 = (10.9.8.7.6) / (120.6) = 42 Habibkhan answered Sep 23, 2017 • selected Sep 23, 2017 by mystylecse Habibkhan comment Share Follow See all 0 reply Please log in or register to add a comment.