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 <[email protected]> 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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
