Level order insert in a binary tree

“We have seen binary search trees, heaps.. how would you normally create a dynamic tree from a list. Simply, you are given an array, you need to convert it into a binary tree in level order.”

Introduction

    Level order traversal needs a level-by-level movement in a tree. But if you want to recreate the tree from an array in a level-order way. It should be easy. Just you need to fill the elements with the correct formula as we already discussed.

       2i             -----> root

2i+1     2i+2    --> left      right

This is the basis for the level order insert.

Concept

   If you check the level order traversal, many uses stacks. But we should avoid using stacks. Instead, we will use recursion for our case.

  Understanding recursion requires a simple base condition which needs to be repeated for different argument.

     for example, if you have an array,

     arr = {0,1,2,3,4,5,6,7,8,9}

the tree becomes like this,

                  0

           1                    2

    3           4           5      6

7     8     9

For 0, we need to create 1 and 2. For 1, 3, 4. For 3, create 7,8. Similarly for 4, create 9.

This means, you need to do recursion left with left index and right with right index. The end condition is when left or right index is exceeding the size of the array.

Code

Tree *tobj;

void level_order_insert(Tree* root, int* arr, int start, int size)

{

    int left = 2*start+1;

    int right = 2*start+2;

    if(left > size || right > size)

        return;

    if(root == NULL) {

        tobj = createNode(arr[start]);

        root = tobj;

    }

    if(root->left == NULL && root->right == NULL) {

        if(left < size)

            root->left = createNode(arr[left]);

        if(right < size)

            root->right = createNode(arr[right]);

    }

    level_order_insert(root->left, arr, left, size);

    level_order_insert(root->right, arr, right, size);

}

main() {

   int A[] = {0,1,2,3,4,5,6,7,8,9}

   level_order_insert(tobj, A, 0, 10);

}

• Before root->left = createNode. You need to make sure that left is still < size. This is to handle the border case
• root->left gets start as all left with all odd numbers
• root->right gets start as all right with all even numbers.
• Most of the times you get partially balanced tree with this method.