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.