Symmetric Tree in JavaScript

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

     1
    / \
  2     2
 / \   / \
3   4 4   3

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

     1
    / \
   2   2
    \   \
     3   3
Input: root = [1,2,2,null,3,null,3]
Output: false

Given tree node:

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Solution 1: Recusive

/**
 * Check if the tree is symmetric
 * @param {TreeNode} root
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isSymmetricRecursive = root => {
  // If the tree is null or undefined, it is symmetric
  if (!root) {
    return true;
  }

  return isMirror(root.left, root.right);
}

/**
 * Check if the left tree and the right tree are symmetric
 * @param {TreeNode} left
 * @param {TreeNode} right
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isMirror = (left, right) => {
  // If both tree are null or undefined, then they are symmetric
  if (!left && !right) {
    return true;
  }

  // If either tree is empty or their values are not equal, then they are not symmetric
  if (!left || !right || left.val !== right.val) {
    return false;
  }

  // Check child left to right, and right to left
  return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}

Solution 2: Iterative

/**
 * Check if the tree is symmetric
 * @param {TreeNode} root
 * @return {boolean}
 * @time complexity: O(n)
 * @space complexity: O(n)
 */
const isSymmetricIterative = root => {
  // Start with root as left and right tree
  const queue = [
    root, // Left
    root, // Right
  ];

  while (queue.length) {
    const left = queue.pop();
    const right = queue.pop();

    // Skip if both tree are empty
    if (!left && !right) {
      continue;
    }

    // Either tree is empty or their values are not equal, then they are not symmetric
    if (!left || !right || left.val !== right.val) {
      return false;
    }

    // Compare left child in the left tree to the right child in the right tree
    queue.push(left.left);
    queue.push(right.right);

    // Compare right child in the left tree to the left child in the right tree
    queue.push(left.right);
    queue.push(right.left);
  }

  return true;
}

Test Case

const assert = require('chai').assert;


class Tree {
  getLeftIndex(index) {
    return index * 2 + 1;
  }

  getRightIndex(index) {
    return index * 2 + 2;
  }

  create(values, index = 0) {
    if (index >= values.length) {
      return null;
    }

    const root = new TreeNode(values[index]);

    root.left = this.create(values, this.getLeftIndex(index));
    root.right = this.create(values, this.getRightIndex(index));

    return root;
  }
}



describe('Symmetric Tree', () => {

  describe('Solution 1: Recursive', () => {
    it('should return true', () => {
      const input = new Tree().create([1,2,2,3,4,4,3]);
      const result = isSymmetricRecursive(input);
      const expected = true;

      assert.strictEqual(result, expected);
    });

    it('should return false', () => {
      const input = new Tree().create([1,2,2,null,3,null,3]);
      const result = isSymmetricRecursive(input);
      const expected = false;

      assert.strictEqual(result, expected);
    });
  });

  describe('Solution 2: Iterative', () => {
    it('should return true', () => {
      const input = new Tree().create([1,2,2,3,4,4,3]);
      const result = isSymmetricIterative(input);
      const expected = true;

      assert.strictEqual(result, expected);
    });

    it('should return false', () => {
      const input = new Tree().create([1,2,2,null,3,null,3]);
      const result = isSymmetricIterative(input);
      const expected = false;

      assert.strictEqual(result, expected);
    });
  });

});

  Symmetric Tree
    Solution 1: Recursive
      ✓ should return true
      ✓ should return false
    Solution 2: Iterative
      ✓ should return true
      ✓ should return false


  4 passing (14ms)