nzoLogic 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




Answer Source

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 values 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