Level order insertion into a binary tree?

Question

Suppose we are given a level order traversal output. How to construct a binary tree from that populated with the data at correct positions?

Please note that I'm not trying to sketch the tree from the given traversal output, but read off the traversal data from an array then populate a binary tree with it by actual coding in C.

Eg:

Let a[] = {A, B, C, D, E, F, G}; //the traversal output in an array

So level-order tree will look like this:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

Suppose there is a tree node structure like so:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

Now I'm trying to read a[] values and code this tree so that it looks like the diagram. There are many examples of level-order traversal but couldn't find anything relevant on actual coding for binary tree construction. This is sort of a "reverse of traversal".

Also please note that this is not homework, though I don't have problems tagging it if more people will notice it that way. :)

Answer 1

For a full (or filling) binary tree it's easy to convert a level traversal into any traversal because the children of a node at position n are at 2n and 2n+1 when the array is 1-indexed and at 2n+1 and 2n+2 when the array is 0-indexed.

So you can easily use that formula to turn it into your favorite traversal order for inserting nodes into a tree (like pre-order).

e.g. recursive psuedocode:

void fill( TreeNode* node, char a[], int arrayLength, int n ){
    // n is the position of the current "node" in the array
    if( n < arrayLength ){
        node->data = a[n];
        fill( node->left, a, arrayLength, 2n+1 );
        fill( node->right, a, arrayLength, 2n+2 );
    }
}

Answer 2

One possible solution:

char a[SIZE] = {A,B,C,D,E,F,G}; 
    node* func(int index){
        if(index < SIZE){
            node *tmp = new node();
            tmp->data = a[index];
            tmp->left = func(2*index + 1);
            tmp->right = func(2*index + 2);
        }
        return tmp;
    }

stacktrace for the tree:

                                     A->a[0]
          B->func(2*0 + 1)=[1]                              C->func(2*0 + 2)=[2]
D->func(2*1 + 1)=[3]    E->func(2*1 + 2)=[4]        F->func(2*2 + 1)=[5]     G->func(2*2 + 2)=[6]

Answer 3

This is like a BFS, so you can use a queue.

Notice that you always assign left child and then immediately after that the right child. So start with a queue containging the root. At each iteration pop the node from the queue and then read the next two values from the array (or stream). Make the first one the left child of the popped node and push it into the queue. Then make the second one a right child and push it into the queue. And so on until there are no elements left in the array (or stream).