c++ - printing all binary trees from inorder traversal

Question

Came across this question in an interview. Given inorder traversal of a binary tree. Print all the possible binary trees from it.

Initial thought:

If say we have only 2 elements in the array. Say 2,1. Then two possible trees are

              2 
               
                1     
    1
   /
   2  

If 3 elements Say, 2,1,4. Then we have 5 possible trees.

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

So, basically if we have n elements, then we have n-1 branches (childs, / or ). We can arrange these n-1 branches in any order. For n=3, n-1 = 2. So, we have 2 branches. We can arrange the 2 branches in these ways:

  /                         /         /
 /               /           

Initial attempt:

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;
    }

}

Answer 1

This problem breaks down quite nicely into subproblems. Given an inorder traversal, after choosing a root we know that everything before that is the left subtree and everthing after is the right subtree (either is possibly empty).

So to enumerate all possible trees, we just try all possible values for the root and recursively solve for the left & right subtrees (the number of such trees grows quite quickly though!)

antonakos provided code that shows how to do this, though that solution may use more memory than desirable. That could be addressed by adding more state to the recursion so it doesn't have to save lists of the answers for the left & right and combine them at the end; instead nesting these processes, and printing each tree as it is found.