Symmetric Tree - Java Solution

1. Introduction

In this post, we address a common problem in binary tree algorithms: determining if a binary tree is symmetric. Symmetry in a binary tree means that the tree is a mirror of itself when divided down its center. This problem is a classic example of using recursion to compare node structures.

Problem

Given the root of a binary tree, the task is to check whether the tree is symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

2. Solution Steps

1. Implement a recursive function to compare nodes of the left subtree with the right subtree.

2. Start with the root and check if the tree is symmetric around the root.

3. Compare nodes at each level, ensuring their values are equal and their subtrees mirror each other.

4. Return true if all corresponding nodes in the subtrees are symmetric.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class SymmetricTree {
    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(isSymmetric(root)); // Test the function
    }

    // Function to check if a tree is symmetric
    public static boolean isSymmetric(TreeNode root) {
        return root == null || isMirror(root.left, root.right);
    }

    // Helper function to check if two trees are mirror images
    private static boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null || right == null) return left == right;
        if (left.val != right.val) return false;

        // Check the outer and inner pairs for symmetry
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

Output:

true

Explanation:

1. isSymmetric: This function checks if the given binary tree is symmetric. It handles the case where the tree is empty and calls isMirror for the root's left and right children.

2. isMirror: A recursive helper function that determines if two subtrees are mirror images of each other. It compares the values of the nodes and checks if the outer and inner pairs of the subtrees are symmetric.

3. The function returns true if both subtrees are null or if their values match and their respective children are mirrors of each other.

4. If any asymmetry is found at any level, the function returns false.

5. This approach efficiently determines the symmetry of the tree by comparing corresponding nodes in the left and right subtrees.