# 101. Symmetric Tree 🔗

**Difficulty**: `Easy` - **Tags**: `Binary Tree`, `DFS`, `BFS`, `Recursion`, `Iteration`

[LeetCode Problem Link](https://leetcode.com/problems/symmetric-tree/)

***

## Problem Statement 📜

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

***

## Examples 🌟

🔹 **Example 1**:

**Input**:

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

**Output**:

```plaintext
true
```

***

🔹 **Example 2**:

**Input**:

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

**Output**:

```plaintext
false
```

***

## Constraints ⚙️

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

***

## Follow-up 🧐

Can you solve it both recursively and iteratively?

***

## Solution 💡

To determine if a binary tree is symmetric:

1. Compare the left and right subtrees to see if they are mirrors of each other.
2. Perform this comparison recursively or iteratively.

***

### Java Solution (Recursive Approach)

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true; // An empty tree is symmetric
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true; // Both nodes are null, symmetric
        }
        if (t1 == null || t2 == null) {
            return false; // One node is null, asymmetric
        }
        return (t1.val == t2.val) // Check values
            && isMirror(t1.left, t2.right) // Compare outer children
            && isMirror(t1.right, t2.left); // Compare inner children
    }
}
```

***

### Java Solution (Iterative Approach)

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();

            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null || t1.val != t2.val) {
                return false;
            }

            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);
        }

        return true; // All nodes are symmetric
    }
}
```

***

## Explanation of the Solutions

1. **Recursive Approach**:
   * Compare the root's left and right subtrees.
   * Recursively check the symmetry of the outer and inner pairs of nodes.
2. **Iterative Approach**:
   * Use a queue to compare nodes in a level-order fashion.
   * Add pairs of nodes to the queue, ensuring the outer and inner children are paired.

***

## Time Complexity ⏳

* **O(n)**, where `n` is the number of nodes in the tree. Each node is visited once.

## Space Complexity 💾

* **O(h)** for the recursive approach, where `h` is the height of the tree (stack space for recursion).
* **O(n)** for the iterative approach due to the queue.

***

## Follow-up Challenges 🧐

* Can you solve this problem for a multi-ary tree?
* What modifications would you make if the tree's symmetry condition depended on node depth?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-9-binary-tree-general/071-symmetric-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.