печать всех бинарных деревьев из обхода по порядку

На этот вопрос наткнулся на интервью. Дан обход двоичного дерева в порядке. Выведите из него все возможные бинарные деревья.

Первоначальная мысль:

Допустим, у нас всего 2 элемента в массиве. Скажите 2,1. Тогда два возможных дерева

              2 
               \
                1     
    1
   /
   2  

Если 3 элемента Скажем, 2,1,4. Тогда у нас есть 5 возможных деревьев.

 2               1            4           2            4
  \             / \          /             \          /
   1           2   4        1               4        2
    \                      /               /          \
     4                    2               1            1

Итак, в основном, если у нас есть n элементов, то у нас есть n-1 ветвей (дочерние элементы, / или). Мы можем расположить эти n-1 ветки в любом порядке. Для n = 3, n-1 = 2. Итак, у нас есть 2 ветки. Мы можем расположить две ветви следующими способами:

  /     \         \           /         /\
 /       \        /           \

Начальная попытка:

struct  node *findTree(int *A,int l,int h)
{
    node *root = NULL;
    if(h < l)
            return NULL;
    for(int i=l;i<h;i++)
    {
            root = newNode(A[i]);
            root->left = findTree(A,l,i-1);
            root->right = findTree(A,i+1,h);
            printTree(root);
            cout<<endl;
    }

}