- Same Tree
- Symmetric Tree

The way approaching these two problems are very similar. Only difference is that Symmetric Tree compares left node to right node.

Recursive Solution 110. Same Tree 101. Symmetric Tree

```
class Solution:
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p == q
```

```
class Solution(object):
def isSymmetric(self, root):
if not root: return True
def check(p, q):
if p and q:
return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)
return p == q
return check(root.left, root.right)
```

As you can see, isSymmetric compare left to right and right to left.

Here is iteration solution.

```
class Solution(object):
def isSameTree(self, p, q):
stack = [(q, p)]
while stack:
n1, n2 = stack.pop()
if n1 and n2 and n1.val != n2.val:
return False
elif n1 and n2:
stack += [(n1.right, n2.right), (n1.left, n2.left)]
elif n1 or n2:
return False
return True
```

```
class Solution(object):
def isSymmetric(self, root):
if not root: return True
stk = [(root.left, root.right)]
while stk:
n1, n2 = stk.pop()
if n1 and n2 and n1.val != n2.val:
return False
elif n1 and n2:
stk += (n1.left, n2.right), (n1.right, n2.left),
elif n1 or n2:
return False
return True
```