Check Symmetrical Binary Tree using JavaScript
Given a binary tree, our task is to check whether it is Symmetrical Binary tree. In other words, we need to check whether the binary tree is a mirror of itself.
Example:
Input: 11
/ \
12 12
/ \ / \
13 14 14 13
Output: True
Input: 11
/ \
12 12
\ \
13 13
Output: False
Below are the approaches to check Symmetrical Binary tree in JavaScript:
Table of Content
- Recursive Approach
- Iterative approach
Recursive Approach
In this approach we recursively check if the left subtree is a mirror of the right subtree. This means we first compare the root values of the subtrees, and then we check if the left child of one subtree is equal to the right child of the other subtree, and vice versa. If all these checks hold true for every node, the tree is symmetric.
Example: To demonstrate Checking Symmetrical Binary tree using recursive approach.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Function to check if two
// subtrees are mirrors of each other
function isMirror(left, right) {
if (left === null && right === null) {
return true;
}
if (left === null || right === null) {
return false;
}
return (left.val === right.val) &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
// Function to check if a tree is symmetric
function isSymmetric(root) {
if (root === null) {
return true;
}
return isMirror(root.left, root.right);
}
// Example usage:
let root = new TreeNode(11);
root.left = new TreeNode(12);
root.right = new TreeNode(12);
root.left.left = new TreeNode(13);
root.left.right = new TreeNode(14);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(13);
console.log(isSymmetric(root));
Output
true
Time Complexity: O(n), where n is the number of nodes in the tree.
Auxiliary Space: O(h), where h is the height of the tree due to the recursive call stack.
Iterative approach
In this approach we use queue to perform a level-order traversal of the tree. First, we enqueue the left and right children of the root. Then, for each pair of nodes dequeued, we compare their values. If they are not equal, the tree is not symmetric. If they are equal, we enqueue their children in the order needed to check symmetry (left child of the first node with right child of the second node, and right child of the first node with left child of the second node). If we successfully process all nodes without finding any asymmetry, the tree is symmetric.
Example: To demonstrate Checking Symmetrical Binary tree using Iterative approach.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
// Function to check if a tree is
// symmetric using iterative approach
function isSymmetric(root) {
if (root === null) {
return true;
}
let queue = [];
queue.push(root.left);
queue.push(root.right);
while (queue.length > 0) {
let left = queue.shift();
let right = queue.shift();
if (left === null && right === null) {
continue;
}
if (left === null || right === null
|| left.val !== right.val) {
return false;
}
queue.push(left.left);
queue.push(right.right);
queue.push(left.right);
queue.push(right.left);
}
return true;
}
// Example usage:
let root = new TreeNode(11);
root.left = new TreeNode(12);
root.right = new TreeNode(12);
root.left.left = new TreeNode(13);
root.left.right = new TreeNode(14);
root.right.left = new TreeNode(14);
root.right.right = new TreeNode(13);
console.log(isSymmetric(root));
Output
true
Time Complexity: O(n), where n is the number of nodes in the tree.
Auxiliary Space: O(n), for the queue used in the level-order traversal.
Contact Us