# 0101. Symmetric Tree

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0101-symmetric-tree)

Given the `root` of a binary tree, *check whether it is a mirror of itself* (i.e., symmetric around its center).
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

Input: root = [1,2,2,null,3,null,3]
Output: false
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
While this problem is easy and straightforward, we should be **careful with the boundary conditions** for both recursive and iterative methods.
{% endhint %}

> **Iterative**

If both nodes are null, move to the next loop without pushing any nodes onto the stack. If one of the nodes is null, return False. If two nodes' values are different, return False.

> **Recursive**

If both nodes are null, return True. If one of the nodes is null, return False.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Tree                               (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [(root.left, root.right)]
        while stack:
            node1, node2 = stack.pop()
            
            # no child nodes, continue instead of pushing null nodes
            if not (node1  or node2): continue
                
            if not (node1 and node2): return False
            if node1.val != node2.val: return False
            
            stack.append((node1.left,  node2.right))
            stack.append((node1.right, node2.left))
            
        return True

        '''
        # ==================================================
        #  Tree                               (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        def isMirror(leftNode, rightNode):
            if not leftNode and not rightNode: return True
            if not leftNode or  not rightNode: return False
            
            return (leftNode.val == rightNode.val)              \
                and isMirror(leftNode.left,  rightNode.right)   \
                and isMirror(leftNode.right, rightNode.left)
        
        return isMirror(root.left, root.right)
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */

    public boolean isMirror(TreeNode node1, TreeNode node2) {
        if(node1 == null && node2 == null) return true;
        if(node1 == null || node2 == null) return false;
        
        return (node1.val == node2.val) && 
               isMirror(node1.left,  node2.right) &&
               isMirror(node1.right, node2.left);
    }
    
    public boolean isSymmetric(TreeNode root) {
        /* base case */
        if(root.left == null && root.right == null) return true;
        
        return isMirror(root.left, root.right);
    }
}
```

{% endtab %}
{% endtabs %}