CODEWITHSUNDEEP
carraysalgorithmbinary-tree
JustaRedShirt
JustaRedShirt

Reputation: 195

Create binary tree in level order from array

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.

Upvotes: 6

Views: 2361

Answers (1)

lrleon
lrleon

Reputation: 2648

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:

  1. The root of general tree is at the position 0
  2. A queue q has the next nodes to be processed
  3. 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
  4. 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;
}

Upvotes: 0

Related Questions