algorithm used
araay = ["10" , "2", "2", "#", "1", "1", "#"]
lets break this down into individual steps
step 1 = ["10"]
step 2 = [ "2", "2" ]
step 3 = ["#", "1", "1", "#"]
check for symmetry in each step except the first one
let's analyze step 3 .
step 3 = ["#", "1", "1", "#"]
split this into two arrays from the middle
step 3 1 = ["#", "1" ]
step 3 2 = ["1", "#"]
Now reverse step 3 2
step 3 2 = ["1", "#"]
now check if step 3 2 is equal to step 3 1
Repeat the above process for each step
If all steps mirror each other, the binary tree is considered a mirror image
const Input = ["10" , "2", "2", "#", "1", "1", "#"];
function isEqual(a,b)
{
// if length is not equal
if(a.length!=b.length)
return false;
else
{
// comapring each element of array
for(var i=0;i<a.length;i++)
if(a[i] !== b[i]){
return false;
}
return true;
}
}
// Response
let symetric = true ;
let stepSymetric = true ;
let mirror = true ;
// length of input
const length = Input.length ;
// const length = 31 ;
// lets create binary tree from it
const totalSteps =
Math.log(length + 1)/Math.log(2) ;
// check for symetric binary tree
function checkInt(n) { return parseInt(n) === n };
symetric = checkInt(totalSteps);
//now check for mirror
let goneArrayLength = 0 ;
for (let i = 0; i < totalSteps; i++) {
const cStep = Math.pow(2,i);
const stepArray = [];
// console.log(goneArrayLength);
// now update the step array
const start = goneArrayLength ;
const end = goneArrayLength + cStep ;
for (let j = start; j < end; j++) {
stepArray.push(Input[j])
}
console.log(stepArray);
// Now we have each step lets find they are mirror image or not
// check for even length
if(stepArray.length%2 !== 0 && i !== 0){
stepSymetric = false ;
}
const partitation = stepArray.length / 2 ;
const leftArray = stepArray.slice(0,partitation);
const rightArray = stepArray.slice(partitation , partitation * 2);
// console.log("leftArray");
// console.log(leftArray);
// console.log("rightArray");
// console.log(rightArray);
function mirrorCheck (){
let check = false;
if(cStep === 1){
return true ;
}
let array1 = leftArray;
let array2 = rightArray.reverse();
// console.log("first");
// console.log(array1);
// console.log("second");
// console.log(array2);
let equal = isEqual(array1 , array2)
// console.log(equal);
check = true ;
if(!equal){
// console.log("Noooooooooooooooo")
check = false ;
}
return check;
}
let mirrorC = mirrorCheck();
if(!mirrorC){
mirror = false;
}
goneArrayLength = goneArrayLength + cStep ;
}
console.log(mirror + " " + symetric + " " + stepSymetric )
if(mirror && symetric && stepSymetric ){
console.log("Mirror Image");
}
else{
console.log("Not mirror image")
}
// console.log(isSymetric);
// console.log(totalSteps);