Symmetric Tree

Given the root of a binary tree, determine if it is a mirror of itself (i.e., symmetric around its center). This problem is fundamental in understanding tree structures and recursion, and it has applications in data validation and pattern recognition.

Problem Description

You are tasked with writing a function that takes the root of a binary tree as input and returns true if the tree is symmetric, and false otherwise.

A binary tree is considered symmetric if the left subtree is a mirror reflection of the right subtree. This means:

1. The root's left child must be equal to the root's right child.
2. The left subtree of the root's left child must be a mirror of the right subtree of the root's right child.
3. The right subtree of the root's left child must be a mirror of the left subtree of the root's right child.

Consider a node's value. For symmetry, the corresponding nodes in the left and right subtrees must have the same value.

Key Requirements:

• The function should correctly identify symmetric and non-symmetric trees.
• It should handle empty trees and trees with a single node.

Expected Behavior:

• If the tree is symmetric, return true.
• If the tree is not symmetric, return false.

Edge Cases to Consider:

• An empty tree (root is null).
• A tree with only a root node.
• Trees where structure is mirrored but values differ.
• Trees where values are mirrored but structure differs.

Examples

Example 1:

Input:
    1
   / \
  2   2
 / \ / \
3  4 4  3

Output: true

Explanation: The left subtree (rooted at the first 2) is a mirror of the right subtree (rooted at the second 2).
- The left child of the left subtree's root (3) matches the right child of the right subtree's root (3).
- The right child of the left subtree's root (4) matches the left child of the right subtree's root (4).

Example 2:

Input:
    1
   / \
  2   2
   \   \
   3    3

Output: false

Explanation: Although the values of the children of the root are the same (2 and 2), their positions and further children do not form a mirror image. The left subtree has a right child (3), while the right subtree has a right child (3). For symmetry, the left subtree should have a right child that mirrors the left child of the right subtree, and vice versa.

Example 3:

Input: null

Output: true

Explanation: An empty tree is considered symmetric by definition.

Example 4:

Input:
    1

Output: true

Explanation: A tree with a single node is considered symmetric.

Constraints

• The number of nodes in the tree is between 0 and 1000.
• Node values are integers.
• The solution should aim for an efficient time complexity.

Notes

• You will likely need a helper function to compare two subtrees for mirror symmetry.
• Consider how you will handle null nodes when traversing.
• Think about both recursive and iterative approaches.