nzoLogic - 3 years ago 116
Javascript Question

# Checking if a binary tree is symmetrical in JavaScript

Given a tree, I'm supposed to check if it's symmetrical, or a mirror of itself down the center. I'm missing one edge case and cannot for the life of me figure out what it is. The only error I get on CodeFights is "Output limit exceeded"

Here's what the example tree looks like

This is the main function isTreeSymmetric assigns its left branch to a variable that invokes the leftBranch function and right branch to the rightBranch function which recursively return an array.

The reason I used two different functions was because it helped me compartmentalize my thinking given that on the left half of the tree I had to go right to left and vice versa for the right half so I didn't get lost in a tree hole.

The last return statement in isTreeSymmetrical then checks if the returned type values are Arrays followed by a ternary that either checks the left and right arrays or checks the equality of variables lb and rb in the case the values were not arrays.

I've been working on this for what feels like eternity! Help please.

``````function isTreeSymmetric(t) {
"use strict";
if(!t || ( (!t.left && !t.right) && t.value)) return true
if(!t.left || !t.right) return false

let left = t.left, right = t.right
let rb = rightBranch(right), lb = leftBranch(left)
console.log(`right branch values are \${rb} | left branch values are \${lb}`)
return Array.isArray( rb || lb ) ?
rb.every( (e, i) => e === lb[i]) :
lb === rb

}

//ON RIGHT BRANCH RETURN CHILDREN LEFT TO RIGHT
function rightBranch(n){
"use strict";
if(!n) return null

let value = n.value
if(!n.left && !n.right) return value

let left = n.left || null, right = n.right || null;

return [value].concat(
rightBranch(left),
rightBranch(right)
)

}

// ON LEFT BRANCH RETURN CHILDREN RIGHT TO LEFT
function leftBranch(n) {
"use strict";
if(!n) return null

let value = n.value
if(!n.left && !n.right) return value

let left = n.left || null, right = n.right || null;

return [value].concat(
leftBranch(right),
leftBranch(left))

}

let t = {
"value": 1,
"left": {
"value": 2,
"left": {
"value": 3,
"left": null,
"right": null
},
"right": {
"value": 4,
"left": null,
"right": null
}
},
"right": {
"value": 2,
"left": {
"value": 4,
"left": null,
"right": null
},
"right": {
"value": 3,
"left": null,
"right": null
}
}
}
console.log(isTreeSymmetric(t)) //true``````

The reason I used two different functions was because it helped me compartmentalize my thinking given that on the left half of the tree I had to go right to left and vice versa for the right half so I didn't get lost in a tree hole.

But there's fundamentally nothing different about handling the left or right sides of your tree. Each L and R is another tree – so all you have to do is compare `(l.left, r.left)` and `(l.right, r.right)`

Below we have a recursive function that creates a tree-like recursive process. It will short-circuit and return `false` as soon as any compared `value`s are not equal.

Instead of using the tree literal you made, I made a simple `Node` constructor to build the tree nodes more easily. This allows me to create a test case for both symmetric and asymmetric trees to verify our function is working correctly

``````const isTreeSymmetric = tree => {
const aux = (l, r) => {
if (l === undefined && r === undefined)
return true
else if (l === undefined || r === undefined)
return false
else if (l.value === r.value)
return aux(l.left, r.left) && aux(l.right, r.right)
else
return false
}
return aux(tree.left, tree.right)
}

const Node = (value, left, right) => ({value, left, right})

const tree1 =
Node(1,
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))),
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))))

const tree2 =
Node(1,
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))),
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(6000))))

console.log(isTreeSymmetric(tree1)) // true
console.log(isTreeSymmetric(tree2)) // false``````

Code re-use

The astute observer will notice that the `aux` function above is check for tree equality – this is a useful function on it's own so it makes sense to define it outside of `isTreeSymmetric`.

This is probably a better way to write our `isTreeSymmetric` function because it's clearer what's happening and promotes function reuse

``````const isTreeEqual = (x, y) => {
if (x === undefined && y === undefined)
return true
else if (x === undefined || y === undefined)
return false
else if (x.value === y.value)
return isTreeEqual(x.left, y.left) && isTreeEqual(x.right, y.right)
else
return false
}

const isTreeSymmetric = tree =>
isTreeEqual(tree.left, tree.right)

const Node = (value, left, right) => ({value, left, right})

const tree1 =
Node(1,
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))),
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))))

const tree2 =
Node(1,
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(5))),
Node(2,
Node(3, Node(4), Node(5)),
Node(3, Node(4), Node(6000))))

console.log(isTreeSymmetric(tree1)) // true
console.log(isTreeSymmetric(tree2)) // false``````

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download