3
\$\begingroup\$

If I want to make a binary tree from an array in the following order:

Example: for the following array: { -1, 17, -1, 3, -1, -1, -1, 55, -1, 4, -1, 15, 11, 2, 3 } the following tree is created:

           55

     15         3

  2     4     *    17

3 11  *   *      *    *

The function is recursive and returns a Tree input: the array and it's size. The tree nodes can only receive positive values from the array so -1 wont be considered. * means NULL prototype: Tree BuildTreeFromArray(int *arr, int size).

Would very much appreciate the help.

This is what I had so far and it's working but I don't really like it.

Tree BuildTreeFromArray(int  *arr, int  size)
{
    Tree resTree;
    Tree right;
    Tree left;
    resTree.root = (TreeNode*)malloc(sizeof(TreeNode));
    checkMemoryAllocation(resTree.root);
    int halfSize;

    if (size == 1)
    {
        resTree.root->data = arr[0];
        resTree.root->left = NULL;
        resTree.root->right = NULL;
    }
    else
    {
        halfSize = size / 2;
    resTree.root->data = arr[halfSize];

    if (arr[halfSize/2] != -1)
    {//we check if there's a valid array data we can input to the tree
        left = BuildTreeFromArray(arr, halfSize);
        resTree.root->left = left.root;
    }
    else
        resTree.root->left = NULL;

    if (arr[halfSize + (halfSize / 2) + 1] != -1)
    {
        right = BuildTreeFromArray(arr + halfSize + 1, halfSize);
        resTree.root->right = right.root;
    }
    else
        resTree.root->right = NULL;

    }
    return resTree;
}

Could this be written in a different version?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$
  • Do not cast the malloc value. It serves no purpose, and may mask a serious problem.

  • Allocating sizeof(TreeNode) assumes the knowledge of the type of resTree.root, and results in the double maintenance. A preferred idiom is malloc(sizeof(*resTree.root)).

  • As written, the node tests for validity of its (future) children. It is more natural for the node to test its own validity:

    if (size == 0) {
        return NULL;
    }
    
    halfSize = size/2;
    if (arr[halfSize == -1) {
        return NULL;
    }
    
    resTree.root = malloc(sizeof(*resTree.root));
    resTree.root->data = data;
    resTree.root->left = BuildTreeFromArray(....).root;
    resTree.root->right = BuildTreeFromArray(....).root;
    
    return resTree;
    
  • I don see a reason why TreeNode is wrapped into Tree. More context would be nice.

\$\endgroup\$
1
\$\begingroup\$

Avoid using recursive function calls in c (or similar languages)

The available calls stack memory will always be a limited resource, and won't fit for an arbitrary depth of function calls (and thus your tree size would be also limited).

You can always avoid using recursion by providing a dynamic stack data structure and an appropriate loop.

Fix your indentation and always use a clear scope

Your indentation is broken and the scope of statements is unclear at several places (my comments starting with !!!):

Tree BuildTreeFromArray(int  *arr, int  size)
{
    // ...
    if (size == 1)
    {
        // ...
    }
    else
    {
        halfSize = size / 2;
    resTree.root->data = arr[halfSize]; // !!! Should be indented according the enclosing scope block
    // ...
    if (arr[halfSize/2] != -1)
    {//we check if there's a valid array data we can input to the tree
       // ...
    }
    else // !!! Missing scope block
        resTree.root->left = NULL; 

    if (arr[halfSize + (halfSize / 2) + 1] != -1)
    {
       // ...
    }
    else // !!! Missing scope block
        resTree.root->right = NULL;

    }
    return resTree;
}

Here's the fully fixed version (I'm not sure that will provide exactly the same logic as you currently have it):

Tree BuildTreeFromArray(int  *arr, int  size)
{
    Tree resTree;
    Tree right;
    Tree left;
    resTree.root = (TreeNode*)malloc(sizeof(TreeNode));
    checkMemoryAllocation(resTree.root);
    int halfSize;

    if (size == 1)
    {
        resTree.root->data = arr[0];
        resTree.root->left = NULL;
        resTree.root->right = NULL;
    }
    else
    {
        halfSize = size / 2;
        resTree.root->data = arr[halfSize];

        if (arr[halfSize/2] != -1)
        {//we check if there's a valid array data we can input to the tree
            left = BuildTreeFromArray(arr, halfSize);
            resTree.root->left = left.root;
        }
        else
        {
            resTree.root->left = NULL;
        }
        if (arr[halfSize + (halfSize / 2) + 1] != -1)
        {
            right = BuildTreeFromArray(arr + halfSize + 1, halfSize);
            resTree.root->right = right.root;
        }
        else
        {
            resTree.root->right = NULL;
        }
    }
    return resTree;
}
\$\endgroup\$
8
  • \$\begingroup\$ Using a dynamic stack data structure is the same as using recursion. The difference you are manually implementing the structure. If you are going to run out of stack space you are probably going to run out of dynamic stack data structure as they both use memory. \$\endgroup\$ May 4, 2017 at 19:29
  • 1
    \$\begingroup\$ @Loki I seriously disagree, since the available stack storage is limited to a way smaller amount of memory than dynamic memory allocation would allow. \$\endgroup\$ May 4, 2017 at 19:31
  • \$\begingroup\$ That is a misunderstanding of how stacks work. Stacks will grow to fill memory. Memory Full => (Dynamically allocated space + Stack space) exceeds addressable space. All modern OS will dynamically increase the amount of space used by there stack as required. \$\endgroup\$ May 4, 2017 at 21:21
  • 1
    \$\begingroup\$ @LokiAstari " All modern OS will dynamically increase the amount of space used by there stack as required." What do you consider falling under that category? FreeRTOS (nope), Embedded Linux (nope), bare metal (nope). \$\endgroup\$ May 4, 2017 at 21:25
  • \$\begingroup\$ Not heard of FreeRTOS. But the other two, yes. Though they don't dynamically allocate; the stack and heap just grow towards each other until they crash together. There is no fixed size. So if we limit our discussion to the point on hand. Dynamically allocate space and growing the stack are basically the same thing. Eventually you run out of space as the total space is the space used by the combination of both. \$\endgroup\$ May 4, 2017 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.