Thread: Fast generation of a binary tree

Hi all,

I am trying to generate a binary tree in C which considers all the possible combination for a number of array elements and a number of different options for each array element.

For example, consider that the array has 3 values which are the following:

Code:

#define NO_OF_IDS 3
Array[NO_OF_IDS] = {“ID1”, “ID2”, “ID3”}

And 2 different option (OPTION 1 and OPTION 2) for each array value.

Then the tree generated should be that:


where “1” stands for “OPTION 0” and “2” for “OPTION 1”.

I can create the above tree manually by using the code below:

Code:

root = newNode(“ROOT”, 0);
/* HEIGHT 1 */
root->left = newNode(&Array[1], 0);
root->right = newNode(&Array[1], 1);
/* HEIGHT 2 */
root->left->left = newNode(&Array[2], 0);
root->left->right = newNode(&Array[2], 1);
root->right->left = newNode(&Array[2], 0);
root->right->right = newNode(&Array[2], 1);
/* HEIGHT 3 */
root->left->left->left = newNode(&Array[3], 0);
root->left->left->right = newNode(&Array[3], 1);
root->left->right->left = newNode(&Array[3], 0);
root->left->right->right = newNode(&Array[3], 1);

root->right->left->left = newNode(&Array[3], 0);
root->right->left->right = newNode(&Array[3], 1);
root->right->right->left = newNode(&Array[3], 0);
root->right->right->right = newNode(&Array[3], 1);

where:

Code:

struct node* newNode(char *String, uint8_t OPTION)
{
    struct node* node = (struct node*)
    malloc(sizeof(struct node));
    node->String = String;
    node->OPTION = OPTION;
    node->left = NULL;
    node->right = NULL;
    return(node);
};

struct node
{
    char* String;
    struct node* left;
    struct node* right;
    uint8_t OPTION;
};

The question is that: Can I create the tree in a faster way for a specific ID number?

Thank you all in advance.

Originally Posted by limp

The question is that: Can I create the tree in a faster way for a specific ID number?

Yes, you can generate that tree using a function which takes, for instance, a root node as argument, an array and its size. Use some recursion for a simple solution.