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)
