## 101. Symmetric Tree

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

For example, this binary tree`[1,2,2,3,4,4,3]`is symmetric:

``````    1
/ \
2   2
/ \ / \
3  4 4  3
``````

But the following`[1,2,2,null,3,null,3]`is not:

``````    1
/ \
2   2
\   \
3    3
``````

Note:
Bonus points if you could solve it both recursively and iteratively.

Thoughts:

1. Recursively: each call needs to check the current two nodes value and need to recursively call two pairs: (left.left, right.right) and (left.right, right.left).
2. Iteratively: Same logic; Using stack, each time check the and push the corresponding pairs of child node into the stack

Code: Recursive

``````public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}

private boolean isSymmetricHelp(TreeNode left, TreeNode right){
if(left==null || right==null)
return left==right;
if(left.val!=right.val)
return false;
return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
}
``````

Code: Iterative

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root.left);
s.push(root.right); // relative ordering in the pair does not matter
TreeNode l, r;

while(!s.empty()){
l = s.pop(); r = s.pop();
if(l == null && r == null) continue;
if(l == null || r == null || l.val != r.val) return false;
s.push(l.left); s.push(r.right); // relative ordering in the pair does not matter
s.push(l.right); s.push(r.left);
}

return true;
}
}
``````