Creating a binary tree in level order from an array

Question

I am working on a small algorithm that builds a binary tree in level order. I have been given an array, and I have to use the values ​​in it to build the binary tree in level order. Example: arr inarr [5] = {1,2,3,4,5};

for such an array, I need to populate the binary tree so that it looks like this:

        1
      /   \
    2      3
   / \    / \
  4   5  *   * 

(* - NULL) nodes are the basic binary nodes with left and right pointer and space for an int that contains a value from an array.

I understand the concept of passing a tree along its height, and you move through it one level at a time, but I'm not sure of the correct logic that will correctly construct it in this way.

Answer 1

A "natural" way of traversing a tree by level is using a queue. Thus, intuitively, an algorithm that does the opposite can use a queue to store the next processed nodes.

Such an algorithm will work with the following principles:

• The root of the common tree is in position 0
• The qfollowing nodes will be processed in the queue .
• Each time we see a node, retrieving from the queue, its children are in positions iand i+1. Note that level traversal guarantees this condition. So
• We put the children of the current node in the queue

The following pseudo-code builds a tree from an array containing its level traversal

Node * build_from_level_order(int a[], int n)
{
  Queue q; // this is a queue of pointers to nodes

  Node * root = (Node*) malloc(sizeof(Node));
  root->key = a[0]; root->left = root->right = NULL;
  q.put(root);

  for (int i = 1; i < n; /* advancing of i is inside */)
    {
      Node * p = q.get();

      Node * l = (Node*) malloc(sizeof(Node));
      l->key = a[i++]; l->left = l->right = NULL;

      p->left = l;
      q.put(l);

      if (i < n) // last level could end in a left node, this test prevents to see an inexistent right node
        {
          Node * r = (Node*) malloc(sizeof(Node));
          r->key = a[i++]; r->left = r->right = NULL;
          p->right = r;
          q.put(r);
        }
    }

  return root;
}