Convert array to complete binary tree

A complete binary tree is a binary tree whose all levels except the last level are completely filled and all the leaves in the last level are all to the left side.

In other words -

A complete binary tree is a binary tree in which all nodes are filled except leaf nodes and leaf nodes are towards left first.

Now let’s think about converting array to complete binary tree -

We know that in array representation of binary tree, the left child for a node exist at index 2i+1 and right child at 2i+2.

This concept can be used to fill nodes and create tree.

Let’s try to understand from above image -

We first try to use first element of array which is at index 0,

so for index = 0

root = array[0]; // 2

root.left = array[2*0+1] // 3

root.right = array[2*0+2] // 6

Let’s write the program now -

class Node {
    constructor(value) {
        this.data = value;
    }
}
class BinaryTree {
    constructor() {
        this.root = null;
    }
   inOrderTraversal() {
        const traverse = (root) => {
            if (root == null) {
                return;
            }
            traverse(root.left);
            console.log(root.data);
            traverse(root.right);
        }
        traverse(this.root);
   }
}
function createCompleteBinaryTreeFromArray(arr) {
    const length = arr.length;
    const binaryTree = new BinaryTree();
    const traverseAndReplace = (root, i) => {
        if (i < length) {
            root = new Node(arr[i]);
            root.left = traverseAndReplace(root.left, 2 * i + 1);
            root.right = traverseAndReplace(root.right, 2 * i + 2);
        }
        return root;
    }
    binaryTree.root = traverseAndReplace(binaryTree.root, 0);
    return binaryTree;
}
const result = createCompleteBinaryTreeFromArray([1, 2, 3, 4, 5, 6, 6, 6, 6]);
result.inOrderTraversal();

In the create method we check if index is less than length & then assign value to root, left and right.