Symmetric Tree - Python Solution

1. Introduction

The "Symmetric Tree" problem is a fundamental question in tree data structures, focusing on determining whether a binary tree is a mirror image of itself. This problem is often encountered in coding interviews and is crucial for understanding tree traversal techniques and symmetry in data 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 and vice versa.

2. Solution Steps

1. Implement a recursive function to compare nodes in the tree.

2. Compare the left subtree of a node with the right subtree of its mirror node.

3. Ensure that the values of mirror nodes are equal and their respective subtrees are symmetric.

4. Handle the base case where both nodes being compared are null.

5. The tree is symmetric if all mirrored pairs of nodes are symmetric.

3. Code Program

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSymmetric(root):
    def isMirror(left, right):
        # Both nodes are null, thus symmetric
        if not left and not right:
            return True
        # Only one of the nodes is null, thus not symmetric
        if not left or not right:
            return False
        # Nodes must have the same value and their subtrees must be mirrors of each other
        return (left.val == right.val and
                isMirror(left.left, right.right) and
                isMirror(left.right, right.left))

    return isMirror(root, root)

# Example Usage
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(3), TreeNode(4))
root.right = TreeNode(2, TreeNode(4), TreeNode(3))
print(isSymmetric(root))

root = TreeNode(1)
root.left = TreeNode(2, None, TreeNode(3))
root.right = TreeNode(2, None, TreeNode(3))
print(isSymmetric(root))

Output:

True
False

Explanation:

1. Recursive Comparison: The isMirror function recursively compares pairs of nodes - one from the left subtree and the other from the right subtree.

2. Symmetry Check: It checks if the nodes have the same value and if their respective left and right subtrees are mirror images of each other.

3. Null Node Handling: The case where both nodes in a pair are null is handled as a base case, indicating symmetry at that level.

4. Non-Symmetric Cases: If one node is null and the other is not, or if their values do not match, the tree is not symmetric.

5. Overall Result: The tree is symmetric if all mirrored node pairs pass the symmetry check.