I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3)Here's my solution:In case 1, we have each node have possibility, 3, 2, 1, respectively,so 3*2*1 = 6 waysIn case 2, we have the same situation, the top node can be 1, 2, 3,three choices, second node two choices, so and so forth, so I get 6waysIn case 3, it is same to case 2 and I get 6 waysIn the end I have 6 + 6 + 6 number of the beast = 18 different threes.(Edited!) Why does this answer from Stackoverflow based on so called Catalan Number only give me 5 trees?
Calculating the number of unique BST generatable from n keys, why is my number so large
trees;probability theory;permutations
You overcounted some of the trees and left out two other possibilities. In your Case 1, for example, there is only one possible BST of that form, namely the one with 2 in the root, 1 in the left subtree and 3 in the right subtree (the leftmost tree below). Remember that you have to maintain the binary search tree condition: a node with value $k$ must have each of the values in its left subtree less than or equal to $k$ and each of the values in the right subtree must be greater than or equal to $k$. As a consequence, a BST with node values $\{1, 2, \dotsc,n\}$ must have inorder traversal equal to $\langle1, 2, \dotsc,n\rangle$. When $n=3$, then, we'll have these five BSTS: 