Symmetric Tree

To solve this coding challenge, we need to determine if a given binary tree is symmetric around its center. Essentially, this means checking if the tree is a mirror image of itself. We will approach this problem with two methods: a recursive solution and an iterative solution using a queue.

Step-by-Step Explanation

# Explanation:

1. Understanding Symmetry in Binary Trees:
• A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
• For two trees to be mirror images:
1. Their root values must be identical.
2. The left subtree of the left tree must be a mirror image of the right subtree of the right tree.
3. The right subtree of the left tree must be a mirror image of the left subtree of the right tree.
2. Base Cases:
• An empty tree is symmetric by definition.
• If only one subtree exists or their root values are not the same, the tree is not symmetric.
3. Recursive Approach:
• Use a helper function to compare corresponding nodes from the left and right subtrees.
• Recursively check all the corresponding children nodes to ensure they mirror each other.
4. Iterative Approach (Using Queue):
• Use a queue to iteratively check pairs of nodes.
• For each pair, enqueue their children in a specific order to simulate the mirroring check.
• If any pair fails the symmetry condition, return false.

Detailed Steps in Pseudocode:

Recursive Approach:

                                            
# Recursive helper function definition
Function isMirror(left_subtree, right_subtree):
    # Base case: both subtrees are empty
    If left_subtree is null And right_subtree is null:
        Return true

    # If only one of the subtrees is empty
    If left_subtree is null Or right_subtree is null:
        Return false

    # If the values of the current nodes don't match
    If left_subtree.value Not equal to right_subtree.value:
        Return false

    # Recursively check the next level of the subtrees:
    # - left subtree's left with right subtree's right
    # - left subtree's right with right subtree's left
    Return isMirror(left_subtree.left, right_subtree.right) And isMirror(left_subtree.right, right_subtree.left)

# Main function to initiate the symmetry check
Function isSymmetric(root):
    # An empty tree is symmetric
    If root is null:
        Return true

    # Use the helper function to compare left and right subtrees
    Return isMirror(root.left, root.right)

                                        

Iterative Approach:

                                            
# Initiating with a queue
Function isSymmetric(root):
    # An empty tree is symmetric
    If root is null:
        Return true

    # Initialize a queue to store nodes for level-order traversal
    Initialize queue with (root.left, root.right)

    # While there are nodes to compare
    While queue is not empty:
        # Dequeue two nodes
        left_subtree, right_subtree = Dequeue queue

        # Both nodes are none, continue checking next pair
        If left_subtree is null And right_subtree is null:
            Continue

        # If only one of the nodes is none or the values don't match
        If left_subtree is null Or right_subtree is null Or left_subtree.value Not equal to right_subtree.value:
            Return false

        # Enqueue children nodes in mirror order
        Enqueue to queue (left_subtree.left, right_subtree.right)
        Enqueue to queue (left_subtree.right, right_subtree.left)

    # If all checks are successful, the tree is symmetric
    Return true

                                        

Summary:

• The recursive approach involves a straightforward comparison using recursive calls.
• The iterative approach leverages a queue for a breadth-first traversal to ensure all paired nodes respect the mirror image property.
• Both methods serve to check if the tree is symmetric by evaluating node values and their respective positions in the tree structure.