Symmetric Tree

Problem Statement

The task is to determine if a given binary tree is symmetric around its center. This essentially means that for a binary tree to be symmetric, the left subtree of every node must be a mirror reflection of the right subtree and vice versa. The concept of symmetry here relates to structure as well as the values contained within the nodes.

Examples

Example 1

Input:

root = [1,2,2,3,4,4,3]

Output:

true

Example 2

Input:

root = [1,2,2,null,3,null,3]

Output:

false

Constraints

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Approach and Intuition

To determine if a binary tree is symmetric, we would need a strategy to recursively (or iteratively using queues) compare nodes of the left subtree with the nodes of the right subtree. Here is the stepwise intuition and approach:

1. If the tree is empty or consists of a single node, it is symmetric.
2. Initiate a recursive function that will compare two nodes: the left child of one and the right child of the other.
3. In each recursive call:
   • Check if both nodes are null. If true, return true (as both being null represents symmetry in structure at that level).
   • If one of them is null and the other is not, return false (asymmetric structure).
   • If both are not null, ensure that the values of the nodes are the same.
   • Continue the recursive comparison by:
     • Comparing the left child of the left node to the right child of the right node and
     • Comparing the right child of the left node to the left child of the right node.
   • Return true if both recursive checks are true; otherwise, return false.

Examples Explanation

• Example 1:

  For the tree structured as [1,2,2,3,4,4,3], the tree is symmetric:

  • The left subtree root (2) with children [3,4] mirrors the right subtree root (2) with children [4,3].
  • Recursively, leaf nodes [3] on the left matches the [3] on the right and [4] on the left matches the [4] on the right.
  • Output is true due to the symmetry.

• Example 2:

  For the tree [1,2,2,null,3,null,3]:

  • The left subtree (2) has no children while the right subtree (2) has a child (3).
  • This asymmetry leads to output false as the structures diverge at the second level itself.

Constraints Reflection

• Each node can carry values from -100 to 100, and this broad range requires careful handling in comparisons but does not affect the method of determining symmetry.
• With nodes count constraint from 1 to 1000, the recursive approach should perform efficiently within these confines, given that each node is visited once.

This recursive approach efficiently checks for symmetry by comparing opposite branches of the tree in tandem, leading to a comprehensive yet direct method for determining tree symmetry.

Solutions

// C++
class Solution {
public:
    bool checkSymmetry(TreeNode* rootNode) {
        queue<TreeNode*> nodesQueue;
        nodesQueue.push(rootNode);
        nodesQueue.push(rootNode);
        while (!nodesQueue.empty()) {
            TreeNode* nodeLeft = nodesQueue.front();
            nodesQueue.pop();
            TreeNode* nodeRight = nodesQueue.front();
            nodesQueue.pop();
            if (nodeLeft == NULL && nodeRight == NULL) continue;
            if (nodeLeft == NULL || nodeRight == NULL) return false;
            if (nodeLeft->val != nodeRight->val) return false;
            nodesQueue.push(nodeLeft->left);
            nodesQueue.push(nodeRight->right);
            nodesQueue.push(nodeLeft->right);
            nodesQueue.push(nodeRight->left);
        }
        return true;
    }
};