Checking if a binary tree is symmetrical in JavaScript

Question

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 1

Enjoy my easiest (non recursive) solution!

const isSymmetric =(root) => {
    if (!root) return true;
    
    const L = [root.left];
    const R = [root.right];
    
    while (L.length && R.length){
        const l = L.pop()
        const r = R.pop()
        
        if (!l !== !r || l?.val !== r?.val) return false;
       
        if (l) {
            L.push(l.left)
            L.push(l.right)
            R.push(r.right)
            R.push(r.left) 
        }
    }
    
    return true;
};

Answer 2

here's a little bit of a simpler version that solves this problem in JavaScript by just doing a level order traversal, hope it helps!

var isSymmetric = function(root) {
    var levels = levelOrder(root)
    for (var x = 1; x < levels.length; x++) {
        var level = levels[x]
        for (var i = 0, j = level.length-1; i < level.length; i++,j--) {
            if (level[i] != level[j]) {
                return false
            }
        }
    }
    return true
};

var levelOrder = function(node) {
    if (node == null) { return []}
    var discovered = [];
    discovered.push(node)
    var levels = levelOrderTraverse(discovered,[])
    return levels
}

function levelOrderTraverse(discovered,elms) {
    var level = []
    for (var i = 0; i < discovered.length; i++) {
        if (discovered[i] != null) {
            level.push(discovered[i].val)
        } else {
            level.push("null")
        }

    }
    elms.push(level);
    var newlyDiscovered = [];
    for (var i = 0; i < discovered.length; i++) {
        if (discovered[i] != null) {
            if (discovered[i].left != null) {
                newlyDiscovered.push(discovered[i].left)
            } else {
                newlyDiscovered.push(null)
            }
            if (discovered[i].right != null) {
                newlyDiscovered.push(discovered[i].right)
            } else {
                newlyDiscovered.push(null)
            }
        }
    }
    if (newlyDiscovered.length > 0) {
        levelOrderTraverse(newlyDiscovered,elms)
    }
    return elms
}

also can be found on my github

Answer 3

You don't actually need to check the nodes or group it in an array. Just do as you and @naomik have done but return isTreeEqual(x.left, y.right) && isTreeEqual(x.right, y.left). This checks value and symmetry (since a right branch to the right needs to be symmetric with a left branch to the left and a left banch going right needs to be symmetric with a right branch going left).

Code:

function isTreeSymmetric(t) {
    if (!t){
        return true
    }
    return isTreeEqual(t.left, t.right)
}

isTreeEqual = function(x, y) {
    if (!x && !y){
        return true
    }
    if (!x || !y){
        return false
    }
    if (x.value === y.value){
        return isTreeEqual(x.left, y.right) && isTreeEqual(x.right, y.left)
    } else {
        return false
    }
} 

Answer 4

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

Answer 5

I better use single function to traverse the children for the given tree. In the code above the sequence of traversing is swaping the values, so it fails to check the symmetric tree condition. Check the following code and let me know if it works for you.

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 = traverseTree(right), lb = traverseTree(left)

    return Array.isArray( rb || lb ) ?
              rb.every( (e, i) => e === lb[i]) :
                lb === rb

}



// ON traverseTree
function traverseTree(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(
    traverseTree(left),
    traverseTree(right))

}

  var tree;

  tree = {
    value: 1,
    left: {
      value: 2,
      left: {
        value: 3
      },
      right: {
        value: 4
      }
    },
    right: {
      value: 2,
      left: {
        value: 3
      },
      right: {
        value: 4
      }
    }
  };

console.log(isTreeSymmetric(tree));