As its required to generate all possible binary trees with the given in-order sequence,
Lets hold all the root nodes of generated binary trees in the form of singly linked list.. The structure of the same would be.. struct rootNodes { struct node *root; // holds the root pointer of a binary tree struct rooNodes *nextNode // holds the pointer to the next 'rootNodes' structure which in turn holds the root of the next generated binary tree... }; CreateNodeRN(struct node * root) is basically used to : 1) create/malloc the struct of type 'rootNodes' taking parameter as the root of the new generated binary tree to be set to 'root' variable. 2) 'nextNode' will be set to NULL / 0; The structure used for binary trees would be: struct node { int data; struct node * left; struct node *right; }; CreateNodeBN(int data) is basically used to : 1) create/malloc the struct of type 'node' taking parameter as the data to be stored in a binary tree node. Code: -------------- // Below code written based on 1-based indexing.. Let the in-order sequence be represented by A[N] // The returned list of rootNodes (i.e. the singly linked list of rootNodes) will have the head pointer act as startpoint/dummy whose 'root' struct variable would be NULL // Call GetListOfBTs(1, N, A); struct rootNodes * GetListOfBTs(int startIndex, int endIndex , int *arr) { struct rootNodes* listOfBTs= CreateNodeRN(NULL); struct rootNodes* tempListOfBTs = listOfBTs; struct node * rootBT = NULL; for (int i =startIndex ; i <=endIndex; ++i) { rootBT = CreateNodeBN(arr[i]); rootBT->left = GenerateBT(startIndex, i-1 , arr); rootBT->right = GenerateBT(i+1,endIndex, arr); tempListOfBTs->nextNode = CreateNodeRN(rootBT); tempListOfBTs = tempListOfBTs->nextNode; } return listOfBTs; } struct node * GenerateBT(int startIndex, int endIndex , int *arr) { if ( startIndex > endIndex) return NULL; struct node * root = NULL; for (int i =startIndex ; i <=endIndex; ++i) { root = CreateNodeBN(arr[i]); root->left = GenerateBT(startIndex, i-1 , arr); root->right = GenerateBT(i+1,endIndex, arr); } return root; } On Dec 29, 8:00 am, Lucifer <sourabhd2...@gmail.com> wrote: > The no. of binary trees that can be generated having n nodes would be: > (2n C n) / (n+1) i.e the catalan no. > > On Dec 28, 12:06 am, bugaboo <bharath.sri...@gmail.com> wrote: > > > > > > > > > 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? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.