Making a binary tree using an array in C

Question

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?

Answer 1

• 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.

Answer 2

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;
}

• Loki Astari: 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.
• πάντα ῥεῖ: @Loki I seriously disagree, since the available stack storage is limited to a way smaller amount of memory than dynamic memory allocation would allow.
• Loki Astari: 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.
• πάντα ῥεῖ: @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).
• Loki Astari: 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.