First fix the traversal,
Traversing means already BST formed ===> no.of BST patterns = no.of different traversals
inserting in BST means either insertion in left sub tree or insertion in right sub tree ,i.e. 2^{x}
it is wrong.... just blindly follow the procedure on the paper.
let take at height=0 (root) ---- 1 choice ---- 1^{st} insertion
2^{nd} new insertion ---> inserting can go either left or right ---- 2 ( just stick the node to left for further analysis )
3 ^{rd} new insertion --->
at height=1, we can insert at right side
at height=2, we can insert at right or left
∴ Therefore 3 choices.... ( just stick the node to right at height=2 for further analysis )
4^{th} new insertion --->
at height=1, we can insert at right side
at height=2, we can insert at left side
at height=3, we can insert at right or left
∴ Therefore 4 choices.... ( just stick the node to left at height=2 for further analysis )
we can conclude that, at nth insertion, there are n choices
Total = 1.2.3.4....n = n!
if you didn't get this,
with 4 nodes ===> 4! permutations formed and note down all
each permutation should be lead to a BST, may it duplicate... you are not interested into no.BST therefore duplicates doesn't matter to you