# Symmetric Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/symmetric-tree)
Canonical: https://scaleengineer.com/dsa/problems/symmetric-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Comcast](https://scaleengineer.com/companies/comcast), [Google](https://scaleengineer.com/companies/google), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex)
---
## Problem
Given the `root` of a binary tree, _check whether it is a mirror of itself_ (i.e., symmetric around its center).

**Example 1:**

![](https://assets.glich.co/dsa/symmetric-tree/image0.jpg) 

**Input:** root = [1,2,2,3,4,4,3]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/symmetric-tree/image1.jpg) 

**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`

**Follow up:** Could you solve it both recursively and iteratively?

# Approaches
## Recursive Approach
This approach uses recursion to solve the problem. The core idea is that a tree is symmetric if its left subtree is a mirror image of its right subtree. We can define a helper function that takes two nodes, `t1` and `t2`, and recursively checks if the subtrees rooted at these nodes are mirrors of each other.
**Time:** O(N), where N is the number of nodes in the tree. We visit each node exactly once. · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** The code is very clean, concise, and elegant.; It's a direct translation of the problem's definition, making it easy to understand and reason about.
**Cons:** For extremely deep trees, this approach could lead to a stack overflow error due to deep recursion. However, given the problem's constraint of 1000 nodes, this is not a practical concern.
### Explanation
A tree is symmetric if the root is null or if its left and right subtrees are mirrors of each other. We can implement a helper function, say `isMirror(t1, t2)`, which takes two nodes as input and returns `true` if the trees rooted at `t1` and `t2` are mirror images. The `isMirror` function works as follows:

1.  If both `t1` and `t2` are `null`, they are symmetric. Return `true`.
2.  If one of `t1` or `t2` is `null` (but not both), they are not symmetric. Return `false`.
3.  If the values of `t1` and `t2` are different, they are not symmetric. Return `false`.
4.  The crucial step is the recursive call: the structure is symmetric only if `t1`'s left child is a mirror of `t2`'s right child AND `t1`'s right child is a mirror of `t2`'s left child. So, we return `isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left)`.

The initial call from the main function `isSymmetric` will be `isMirror(root.left, root.right)`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // Both are null, which is symmetric
        if (t1 == null && t2 == null) {
            return true;
        }
        // One is null, but not the other, not symmetric
        if (t1 == null || t2 == null) {
            return false;
        }
        // Values must be equal, and subtrees must be mirrors
        return (t1.val == t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }
}
```
### Algorithm
1. If the `root` is `null`, the tree is symmetric by definition, so return `true`.
2. Create a helper function `isMirror(TreeNode t1, TreeNode t2)` that takes two nodes and checks if the subtrees rooted at them are mirror images.
3. **Base Cases** for the recursion within `isMirror`:
    - If both `t1` and `t2` are `null`, they are symmetric. Return `true`.
    - If one of the nodes is `null` but the other isn't, they cannot be mirrors. Return `false`.
    - If the values of the nodes `t1.val` and `t2.val` are not equal, they are not mirrors. Return `false`.
4. **Recursive Step**: For the subtrees to be mirrors, the left child of `t1` must be a mirror of the right child of `t2`, AND the right child of `t1` must be a mirror of the left child of `t2`. The function should return the result of `isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left)`.
5. The initial call from the `isSymmetric` function will be `isMirror(root.left, root.right)`.

## Iterative Approach using a Queue
As an alternative to recursion, we can solve the problem iteratively using a queue. This approach mimics a breadth-first search (BFS) by comparing nodes at each level. We add pairs of nodes (one from the left subtree, one from the right) to the queue and check them for symmetry.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the binary tree. The space is used by the queue. In the worst case of a complete binary tree, the last level can contain up to N/2 nodes, making the space complexity O(N).
**Pros:** Avoids recursion, thus preventing any risk of stack overflow, making it more robust for very deep trees.; Can be more space-efficient for certain tree structures, such as a skewed tree where its space complexity is O(1) while recursion's is O(N).
**Cons:** The code can be slightly more complex to write and follow compared to the recursive solution.; For a perfectly balanced tree, this approach may use more space (O(N)) compared to the recursive approach (O(log N)).
### Explanation
Instead of relying on the function call stack for recursion, we can use an explicit `Queue` to manage the pairs of nodes that need to be compared. This approach is often preferred to avoid potential stack overflow issues.

The algorithm works as follows:

1.  Initialize a queue and add the root's left and right children. These are the first two nodes to compare.
2.  Loop while the queue is not empty. In each step, we poll two nodes from the queue.
3.  Let the two nodes be `t1` and `t2`. We apply the same checks as in the recursive approach:
    - If both are `null`, they are symmetric, and we continue.
    - If one is `null` or their values differ, the tree is not symmetric, and we return `false`.
4.  If the nodes `t1` and `t2` are a symmetric pair, we then add their children to the queue for the next level of checks. Crucially, we must add them in a mirrored order: `t1.left` is paired with `t2.right`, and `t1.right` is paired with `t2.left`.
5.  If the queue becomes empty, it means we have successfully compared all the necessary pairs without finding any asymmetry, so the tree is symmetric.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);

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

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

            // Enqueue in mirrored order
            queue.add(t1.left);
            queue.add(t2.right);
            queue.add(t1.right);
            queue.add(t2.left);
        }
        return true;
    }
}
```
### Algorithm
1. If the `root` is `null`, return `true`.
2. Initialize a `Queue` (e.g., a `LinkedList`) to store nodes for comparison.
3. Add the root's left child and right child to the queue. These are the first pair to be compared.
4. Start a loop that continues as long as the queue is not empty.
5. Inside the loop, dequeue two nodes, `t1` and `t2`.
6. If both `t1` and `t2` are `null`, this pair is symmetric, so `continue` to the next iteration.
7. If one of the nodes is `null` (but not both), or if their values `t1.val` and `t2.val` are different, the tree is not symmetric. Return `false`.
8. If the nodes are valid so far, enqueue their children in a mirrored order for future comparison: add `t1.left` and `t2.right` to the queue, then add `t1.right` and `t2.left`.
9. If the loop completes without returning `false`, it means all corresponding nodes matched, and the tree is symmetric. Return `true`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isSymmetric ( TreeNode root ) { return dfs ( root , root ); } private boolean dfs ( TreeNode root1 , TreeNode root2 ) { if ( root1 == null && root2 == null ) { return true ; } if ( root1 == null || root2 == null || root1 . val != root2 . val ) { return false ; } return dfs ( root1 . left , root2 . right ) && dfs ( root1 . right , root2 . left ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric =
  function (root) {
    function dfs(root1, root2) {
      if (!root1 && !root2) return true;
      if (!root1 || !root2 || root1.val != root2.val) return false;
      return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
    }
    return dfs(root, root);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSymmetric ( TreeNode * root ) { function < bool ( TreeNode * , TreeNode * ) > dfs = [ & ]( TreeNode * root1 , TreeNode * root2 ) -> bool { if ( ! root1 && ! root2 ) return true ; if ( ! root1 || ! root2 || root1 -> val != root2 -> val ) return false ; return dfs ( root1 -> left , root2 -> right ) && dfs ( root1 -> right , root2 -> left ); }; return dfs ( root , root ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isSymmetric ( self , root : Optional [ TreeNode ]) -> bool : def dfs ( root1 , root2 ): if root1 is None and root2 is None : return True if root1 is None or root2 is None or root1 . val != root2 . val : return False return dfs ( root1 . left , root2 . right ) and dfs ( root1 . right , root2 . left ) return dfs ( root , root )
```