Introduction & Problem Explanation

The Symmetric Tree problem asks us to check whether a binary tree is a mirror of itself (i.e., symmetric around its center).

For example, the tree: 

              1
             / \
            2   2
           / \ / \
          3  4 4  3
is symmetric. However, the tree: 
              1
             / \
            2   2
             \   \
             3    3
is not symmetric. This problem checks understanding of structural symmetry and simultaneous traversal of multiple subtrees.

Illustration of checking Symmetric Tree via mirror path comparison in Java
Real-World Analogy: The Butterfly Wings Match

Imagine looking at a butterfly's wings. For the butterfly to be symmetric, every pattern on the outer edge of the left wing must match the pattern on the outer edge of the right wing, and every pattern on the inner edge of the left wing must match the pattern on the inner edge of the right wing. In terms of a binary tree, this means the left child of the left node must match the right child of the right node, and the right child of the left node must match the left child of the right node. By checking these corresponding mirror paths, we can determine symmetry!

The Algorithmic Approach

1. Recursive Mirror Check (O(n) Time, O(h) Space)

We write a helper function isMirror(TreeNode t1, TreeNode t2) that compares two subtrees.

  • If both nodes are null, they are symmetric mirrors. We return true.
  • If only one of them is null (or if their values are different), they are not symmetric. We return false.
  • Otherwise, we recursively check:
    1. If the outer children are mirrors: isMirror(t1.left, t2.right).
    2. If the inner children are mirrors: isMirror(t1.right, t2.left).
This visits each node once, resulting in O(n) time complexity. The space complexity is O(h) due to the call stack size.

Step-by-Step Execution Walkthrough

Let's trace the recursive mirror check on the tree [1, 2, 2, 3, 4, 4, 3]:

  1. Step 1 (Root call):
    • If the root is null, we return true. It is not.
    • We call the helper: isMirror(root.left, root.right), which is isMirror(node2_left, node2_right).
  2. Step 2 (Compare Left & Right subtrees):
    • Both nodes have value 2. We proceed.
    • We must check the outer children: isMirror(node2_left.left, node2_right.right) which compares node 3 (left) and node 3 (right).
    • We must check the inner children: isMirror(node2_left.right, node2_right.left) which compares node 4 (left) and node 4 (right).
  3. Step 3 (Check Outer matches): We evaluate isMirror(node3_left, node3_right):
    • Both are leaf nodes with value 3. Their recursive sub-calls return true.
    • So outer check returns true.
  4. Step 4 (Check Inner matches): We evaluate isMirror(node4_left, node4_right):
    • Both are leaf nodes with value 4. Their sub-calls return true.
    • So inner check returns true.
  5. Step 5 (Completion): Since both checks return true, the tree is successfully verified as symmetric around its center. We return true.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (t1 == null && t2 == null) return true;: The base case representing two matched empty subtrees.
  • if (t1 == null || t2 == null) return false;: Catches structural mismatches where one side has a node and the other does not.
  • isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left): The core mirror comparison logic, matching outer elements and inner elements of the subtrees recursively.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class SymmetricTree {

    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    // Recursive Mirror Check - O(n)
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }

    public static void main(String[] args) {
        SymmetricTree solver = new SymmetricTree();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.right.right = new TreeNode(3);

        System.out.println("--- Symmetric Tree Demonstration ---");
        System.out.println("Is Symmetric: " + solver.isSymmetric(root));
    }
}

Conclusion

Solving the Symmetric Tree problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.