Description:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
Solution:
Time Complexity : O(n)
Space Complexity: O(n)
// Recursive solution
// Look at both children at the same time and check if they are a mirror image
var isSymmetric = function(left, right = left) {
// Check for the base cases where a child is null or if both children are null
if(left === null && right === null) return true;
if(left === null || right === null) return false;
// Check if the mirror node vals are the same
// If they are then continue checking children nodes
return left.val === right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
};
// Iterative solution
// Breadth first search approach
// Push in child nodes in mirror order
// Make sure each mirror node val is equivalent
var isSymmetric = function(root) {
// Create the queue and add root node twice
// Each instance reference represents one side of the tree
const q = [];
q.push(root);
q.push(root);
while(q.length) {
// Get the current nodes to check
const left = q.pop();
const right = q.pop();
// Use the same logic in the recursive solution
if(left === null && right === null) continue;
if(left === null || right === null) return false;
if(left.val !== right.val) return false;
q.push(left.left);
q.push(right.right);
q.push(left.right);
q.push(right.left);
}
return true;
};
Top comments (0)