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

+1 vote
103 views
Given inorder traversal of a binary tree. Print all the possible binary trees from it?
posted Dec 21, 2015
Share this question

1 Answer

+1 vote
``````#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;
}
``````
answer Dec 22, 2015
Similar Questions
+5 votes

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?