 # 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 => {
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)
`````` Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.