> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-05-2022-101.-symmetric-tree.md).

# 04/05/2022 101. Symmetric Tree

Method: to decide if a tree is symmetric, we have to check for a node, if its left subtree is the reflection of the right subtree. For example, if left subtree and right subtree both have two children. Then the left subtree. left node value should be the same with the right subtree.right node value and the vice versa. So we write a recursive function compare. The base condition is to check if the left and right node are null. If they are both null, return true. If they both are not null, we should check its value. When their values are same. We need further to check if their children are mirrored. We check its outside (left.left right.right) and its inside (left.right and right.left) and only they both true, we can return true.

Time O(N)

Space O(H)

```
// Some code
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
        
    }
    
    private boolean compare(TreeNode left, TreeNode right){
        if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left == null && right == null) return true;
        else if (left.val != right.val) return false;
        
        boolean outside = compare(left.left, right.right);
        boolean inside = compare (left.right, right.left);
        return outside && inside;   
        
    }
}
```

```
// Some code

class Solution {
    public boolean isSymmetric(TreeNode root) {
       if (root == null) return true;
        Queue<TreeNode> queque = new LinkedList<>();
        queque.offer(root.left);
        queque.offer(root.right);
        while (!queque.isEmpty()) {
            TreeNode leftNode = queque.poll();
            TreeNode rightNode = queque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }

            if (leftNode == null || rightNode == null)  {
                return false;
            }
            
            if (leftNode.val != rightNode.val) return false;
            queque.offer(leftNode.left);
            queque.offer(rightNode.right);
            queque.offer(leftNode.right);
            queque.offer(rightNode.left);
        }
        return true;
        
    }
}
```