> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/symmetric-tree.md).

# 101. Symmetric Tree

### Description

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

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/symmetric-tree-tree-which-is-mirror-image-of-itself/)
* [Leetcode](https://leetcode.com/problems/symmetric-tree/)
* [ProgramCreek](https://www.programcreek.com/2014/03/leetcode-symmetric-tree-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[1, 2, 2, 3, 4, 4, 3]

<div align="left"><img src="/files/-MFpYZl0Aj7F34ZhpTaA" alt=""></div>

**Output:** true
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[1, 2, 2, null, 3, null, 3]

<div align="left"><img src="/files/-MFpYNaGnB41Ns-l3aqM" alt=""></div>

**Output:** false
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n). Because we traverse the entire input tree once, the 
 *    total run time is O(n), where n is the total number of nodes in the tree.
 * Space complexity : The number of recursive calls is bound by the height of 
 *    the tree. In the worst case, the tree is linear and the height is in O(n). 
 *    Therefore, space complexity due to recursive calls on the stack is O(n) 
 *    in the worst case.
 */

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isMirror(root.left, root.right);
    }
    
    private boolean isMirror(TreeNode node1, TreeNode node2) {
        if(node1 == null && node2 == null) return true;
        
        if(node1 == null || node2 == null) return false;
        
        if(node1.val != node2.val) return false;
        
        return isMirror(node1.left, node2.right) && 
                isMirror(node1.right, node2.left);
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n). Because we traverse the entire input tree once, the 
 *    total run time is O(n), where n is the total number of nodes in the tree.
 * Space complexity : There is additional space required for the search queue. 
 *    In the worst case, we have to insert O(n) nodes in the queue. Therefore, 
 *    space complexity is O(n).
 */

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if(node1 == null && node2 == null) continue;
            if(node1 == null || node2 == null) return false;
            if(node1.val != node2.val) return false;
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*