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