Given inorder traversal of a binary tree. Print all the possible binary trees from it?

Question

I came to know that ,construction of BST is possible by using PreOrder and PostOrder traversal but is it possible to construct a BST using InOrder traversal , if not then why?

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
using namespace std;

// node structure
struct node
{
    int key;
    struct node *left, *right;
};

map<int, int> mp; 

// A utility function to create a new BST node
struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do preorder traversal of BST
void preorder(struct node *root)
{
    if (root != NULL)
    {
        printf("%d ", mp[root->key]);            //  remapping while printing
        preorder(root->left);
        preorder(root->right);
    }
}

// A utility function to do preorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", mp[root->key]);            //  remapping while printing
        inorder(root->right);
    }
}

// function for constructing trees
vector<struct node *> constructTrees(int start, int end) 
{
    vector<struct node *> list;
    /* if start > end then subtree will be empty so returning NULL in the list */
    if (start > end) 
    {
        list.push_back(NULL);
        return list;
    }

    /* iterating through all values from start to end for constructing left and right subtree recursively */
    for (int i = start; i <= end; i++) 
    {
        /* constructing left subtree */
        vector<struct node *> leftSubtree = constructTrees(start, i - 1);

        /* constructing right subtree */
        vector<struct node *> rightSubtree = constructTrees(i + 1, end);

        /* now looping through all left and right subtrees and connecting them to ith root below */
        for (int j = 0; j < leftSubtree.size(); j++) 
        {
            struct node* left = leftSubtree[j];
            for (int k = 0; k < rightSubtree.size(); k++) 
            {
                struct node * right = rightSubtree[k];
                struct node * node = newNode(i);         //  making value i as root
                node->left = left;                       //  connecting left subtree
                node->right = right;                     //  connecting right subtree
                list.push_back(node);                    //  adding this tree to list
            }
        }
    }
    return list;
} 

// Driver Program to test above functions
int main()
{
    int in[] = {4, 5, 7, 8, 10};
    int N = sizeof(in) / sizeof(int);

    for(int i = 1; i <= N; i++)
        mp[i] = in[i - 1];                   // mapping all numbers from 1 to N for simplicity

    vector<struct node *> totalTreesFrom1toN = constructTrees(1, N);

    /* printing preorder of all BSTs */
    for (int i = 0; i < totalTreesFrom1toN.size(); i++)
    {
        preorder(totalTreesFrom1toN[i]);
        printf("\n");
    }
    return 0;
}