Check whether a Tree is a Mirror-Tree

Given a binary tree, write a program to check if it is a mirror of itself (i.e., symmetric around its center). A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Input/Output Examples

plaintext
Example 1:
Input:

     1
    / \
   2   2
  / \ / \
 3  4 4  3

Output:
True
Explanation: The given tree is symmetric because the left and right subtrees are mirrors of each other.
Example 2:
Input:

     1
    / \
   2   2
    \    \
    3     3

Output:
False
Explanation: The given tree is not symmetric because the structure of the left and right subtrees is not a mirror image.

Approach to Check Whether a Tree is a Mirror-Tree

  1. Recursive Approach:
    • Write a helper function that takes two trees as input and checks if they are mirrors of each other.
    • For two trees to be mirrors:
      • The root values of both trees should be the same.
      • The left subtree of the first tree should be a mirror of the right subtree of the second tree, and vice versa.
  2. Base Case:
    • If both subtrees are null, they are mirrors of each other.
    • If one subtree is null and the other is not, they are not mirrors.
  3. Final Check:
    • Call the helper function by passing the left and right subtrees of the root node. If the helper function returns true, the tree is symmetric.

C++ Program to Check Whether a Tree is a Mirror-Tree

cpp
#include <iostream>
using namespace std;

// Definition of a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

// Function to check if two trees are mirror images of each other
bool isMirror(TreeNode* tree1, TreeNode* tree2) {
    if (tree1 == NULL && tree2 == NULL) {
        return true;
    }
    if (tree1 == NULL || tree2 == NULL) {
        return false;
    }

    // Check if the current nodes and their respective subtrees are mirrors
    return (tree1->data == tree2->data) &&
           isMirror(tree1->left, tree2->right) &&
           isMirror(tree1->right, tree2->left);
}

// Function to check if the tree is a mirror of itself
bool isSymmetric(TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return isMirror(root->left, root->right);
}

int main() {
    // Create a sample tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);

    // Check if the tree is a mirror-tree
    if (isSymmetric(root)) {
        cout << "The tree is symmetric (Mirror-Tree)." << endl;
    } else {
        cout << "The tree is not symmetric (Mirror-Tree)." << endl;
    }

    return 0;
}

Java Program to Check Whether a Tree is a Mirror-Tree

java
// Definition of a binary tree node
class TreeNode {
    int data;
    TreeNode left, right;

    TreeNode(int val) {
        data = val;
        left = right = null;
    }
}

public class MirrorTreeCheck {

    // Function to check if two trees are mirror images of each other
    public static boolean isMirror(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null && tree2 == null) {
            return true;
        }
        if (tree1 == null || tree2 == null) {
            return false;
        }

        // Check if the current nodes and their respective subtrees are mirrors
        return (tree1.data == tree2.data) &&
               isMirror(tree1.left, tree2.right) &&
               isMirror(tree1.right, tree2.left);
    }

    // Function to check if the tree is a mirror of itself
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    public static void main(String[] args) {
        // Create a sample tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        // Check if the tree is a mirror-tree
        if (isSymmetric(root)) {
            System.out.println("The tree is symmetric (Mirror-Tree).");
        } else {
            System.out.println("The tree is not symmetric (Mirror-Tree).");
        }
    }
}

Python Program to Check Whether a Tree is a Mirror-Tree

python
# Definition of a binary tree node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to check if two trees are mirror images of each other
def is_mirror(tree1, tree2):
    if tree1 is None and tree2 is None:
        return True
    if tree1 is None or tree2 is None:
        return False

    # Check if the current nodes and their respective subtrees are mirrors
    return (tree1.data == tree2.data and
            is_mirror(tree1.left, tree2.right) and
            is_mirror(tree1.right, tree2.left))

# Function to check if the tree is a mirror of itself
def is_symmetric(root):
    if root is None:
        return True
    return is_mirror(root.left, root.right)

# Example usage
if __name__ == "__main__":
    # Create a sample tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(3)

    # Check if the tree is a mirror-tree
    if is_symmetric(root):
        print("The tree is symmetric (Mirror-Tree).")
    else:
        print("The tree is not symmetric (Mirror-Tree).")
  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once to check if the two subtrees are mirrors of each other.
  • Space Complexity: O(h), where h is the height of the tree. This space is required for the recursive call stack. In the worst case (for a skewed tree), the space complexity is O(n).

DSA

7314

582

Related Articles