Horje
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

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.

JavaScript 
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.

JavaScript 
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.


 


Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program to Print all Nodes that do not have any Siblings JavaScript Program to Print all Nodes that do not have any Siblings
Print the nodes having exactly one child in a Binary tree using JavaScript Print the nodes having exactly one child in a Binary tree using JavaScript
Moment.js Moment.js
How to Fix JavaScript TypeError: Cannot Set Properties of Undefined? How to Fix JavaScript TypeError: Cannot Set Properties of Undefined?
Lodash Tutorial Lodash Tutorial

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 16



 

Horje