Create binary tree in level order from array

Question

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

given an array like this I need to fill in a binary tree to look like this:

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

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

I understand the concept of traversing the tree based on it's height and you move through it one level at a time, but I am unsure of the correct logic that builds it in this way correctly.

build an empty tree in O(n) and if your array is sorted then you can traverse it in-order and fill the nodes accordingly. The tree you build is a full binary tree with deleting leaves from the right so match your array size — ThunderWiring
@FireSun I checked the post that you report as possible duplicate and the truth is that I find no relationship. Could you please check? — lrleon
Would the same tree be built if arr inarr[5]={3,1,2,4,5};? — chux - Reinstate Monica

lrleon lrleon · Accepted Answer · 2015-11-22T15:42:11

The "natural" way for traversing a tree by levels is using a queue. So, intuitively, an algorithm that does the inverse could use a queue for memorize the next nodes to be processed.

Such algorithm would work with the following principles:

The root of general tree is at the position 0
A queue q has the next nodes to be processed
Each time we see a node, by extracting from the queue, its children are at positions i and i+1. Note that level traversal guarantees this condition. So
We put the children of current node at the queue

The following pseudo code builds the tree from an array containing its by levels 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;
}

Create binary tree in level order from array

1 Answers