# 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).

**Link:** [https://leetcode.com/problems/symmetric-tree/description/](https://leetcode.com/problems/symmetric-tree/description/)

### **Problem Explanation with examples:-**

**Example 1**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678683446565/67d668cc-de59-428d-88c4-f6684447cf03.jpeg align="center")

```markdown
Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: The above binary tree is symmetric because its left and right halves are mirror images of each other.
```

**Example 2**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678683459691/6bd777d5-265c-47e8-af1b-c8aed8521993.jpeg align="center")

```markdown
Input: root = [1,2,2,null,3,null,3]
Output: false
Explanation: The above binary tree is not symmetric because its left and right halves are not mirror images of each other.
```

**Constraints**

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

### Intuition:-

* We have to check for symmetry till the leaf nodes.
    
* We can use recursion to check for symmetry.
    
* A tree is symmetric if the left subtree is a mirror image of the right subtree.
    
* So, a helper function is required to check for the symmetry between two given trees.
    
* The helper function will take two trees as input and will return True if the trees are symmetric and False otherwise.
    

### Solution:-

* First, we check if the root is null. If it is, then we return true.
    
* Then, we define a Mirror function.
    
* The function takes two arguments, a and b which are the left and right subtrees respectively.
    
* If both a and b are null, then we return true.
    
* If either a or b is null, then we return false.
    
* If the values of a and b are equal, then we recursively call the function with `a.left` and `b.right` and then with `a.right` and `b.left`.
    
* If the values of a and b are not equal, then we return false.
    
* Finally, we return the function call with `root.left` and `root.right` as arguments.
    

### Code:-

JAVA Solution

```java
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Mirror(root.left, root.right);
    }

    public boolean Mirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null) {
            return false;
        }
        return a.val == b.val && Mirror(a.left, b.right) && Mirror(a.right, b.left);
    }
}
```

Python Solution

```python
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        def Mirror(a,b):
            if not a and not b: return True
            if not a or not b: return False

            if a.val == b.val and Mirror(a.left,b.right) and Mirror(a.right,b.left): return True

        return Mirror(root.left,root.right)
```

### Complexity Analysis:-

**TIME**:-

Time complexity is **O(n)** where n is the number of nodes in the binary tree. This is because the `Mirror()` function is called recursively on each pair of corresponding nodes in the left and right subtrees of the root node, which visits every node exactly once.

**SPACE**:-

Space complexity is **O(h)**where h is the height of the binary tree. This is because the recursive calls to `Mirror()` is placed on the call stack, and the maximum depth of the call stack is equal to the height of the binary tree. In the worst case, when the binary tree is completely unbalanced, the height could be equal to n, resulting in a space complexity of O(n). However, in a balanced binary tree, the height is log(n), resulting in a space complexity of **O(log(n))**.

### References:-

* [**Recursion**](https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/)
    
* [**Binary Tree**](https://www.geeksforgeeks.org/binary-tree-data-structure/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)