Count of binary trees, given inorder traversal.

Given an inorder traversal only for a binary tree (not necessarily a BST), give a pseudo code to generate all possible binary trees for this traversal sequence.
Firstly, how many binary trees can be generated given an in-order traversal? I know that given 'n' nodes, number of BTs possible is (2^n)-n. But if we are given a specific in-order sequence, can we cut down on this number?


Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.


If you need to build all those Trees, then there are 3 ways a new node N could be added to the already existing set of Tree(s) T to preserve the inorder sequence.
1. N could be added as the rightmost child of tree T.
2. N could be root and T as its left subtree.
3. The right subtree of T say R could be added as left subtree of N and then N added as the right subtree of T.