Symmetric Binary Tree (Mirror Image of Itself) Problem - Java Solution

1. Introduction

This blog post discusses how to determine if a binary tree is symmetric around its center. Symmetry in a binary tree means the tree is a mirror image of itself. This problem is a typical interview question that tests understanding of binary tree properties and recursion in Java.

Problem

Given a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

2. Solution Steps

1. If the tree is empty, it is symmetric.

2. Create a helper function to compare two nodes for symmetry.

3. The helper function will check if both nodes are null (symmetric), one of them is null (not symmetric), or if their values are different (not symmetric).

4. Recursively check the left child of one node with the right child of the other node and vice versa.

5. The main function calls this helper with the root's left and right children.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        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);

        System.out.println("Is symmetric: " + isSymmetric(root));
    }

    // Method to check if a tree is symmetric
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) return true; // An empty tree is symmetric
        return isMirror(root.left, root.right); // Check if left and right subtrees are mirrors
    }

    // Helper method to check if two subtrees are mirrors
    public static boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true; // Both subtrees are empty
        if (t1 == null || t2 == null) return false; // Only one subtree is empty
        if (t1.val != t2.val) return false; // Values at nodes are different

        // Recursively check if the subtrees are mirrors
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}

Output:

Is symmetric: true

Explanation:

In this example, the binary tree is symmetric around its center. The isSymmetric method checks whether the tree is symmetric by comparing the left and right subtrees. It uses a helper method isMirror to compare corresponding nodes in the two subtrees. The tree's left subtree (2 -> 3, 4) is a mirror image of its right subtree (2 -> 4, 3), so the output is true.