## Approach #1 Recursion [Accepted]

**Intuition**

#### Classify possible cases

Case 1: both nodes are `None`

, return `True`

Case 2: one of nodes is `None`

, return `False`

Case 3: both values are not equal, return `False`

Case 4: both values are equal, return `True`

#### how to build up recursion call

- We need 2 recursion calls, one for left subtree, and the other is for right subtree
- We use
`and`

to join both calls- if at least one call returns
`False`

, return`False`

- if both calls return
`True`

, return`True`

- if at least one call returns
`return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)`

#### Why don't we need case 4 in the code

- if we return all cases, how can we go further?
- case 4 end up becoming one of case 1~3 in the end

**Algorithm**

- We set up return case 1~3
- We examine subtree recursively.

**Python**

```
class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
elif p is None or q is None:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
```

**Complexity Analysis**

- Time complexity : $$O(min(p, q))$$.

We won't traverse to additional part, so it only takes minimal number of nodes in `p`

and `q`

.

- Space complexity : $$O(1)$$.

We don't use any additional memory space.

#### Note: you can also choose case 4 over case 3

```
if p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False # if p.val != q.val
```

#### Concise way

```
def isSameTree(self, p, q):
if p is None and q is None:
return True
if p is not None and q is not None:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return False
```

## Approach #2 Level order traversal using stack [Accepted]

**Intuition**

We traverse both trees simultaneously and compare the values whenever we `pop`

item from stack.

We `append`

the pair of identical nodes into stack which is waiting for the next `pop`

.

**Algorithm**

- initialize stack with
`p`

and`q`

- if stack has any pairs, we
`pop`

them and compare them - there are 4 cases we need to consider
- both nodes are
`None`

, we proceed to next pair in stack - only one node is
`None`

, we have to return`False`

- values of both nodes are same, we can proceed to consider subtree in both nodes
- values of both nodes are different, we have to return
`False`

- both nodes are
- after all, if we still didn't return any
`False`

, it means we have two identical trees.

**Python**

```
def isSameTree_stack(self, p, q):
stack = [(p, q)]
while stack:
p_node, q_node = stack.pop()
if p_node is None and q_node is None:
continue
elif p_node is None or q_node is None:
return False
if p_node.val == q_node.val:
stack.append((p_node.left, q_node.left))
stack.append((p_node.right, q_node.right))
if p_node.val != q_node.val:
return False
return True
```

**Complexity Analysis**

- Space complexity : $$O(p U q)$$

- We need stack s for storing pair of
`p`

and`q`

. - if some node is in
`p`

instead in`q`

, it may cause`stack.append(p.some_node, None)`

So it could be looked like:

`[(p, q), (p, None), (None, q)...]`

So the complexity is union of `p`

and `q`

- Time complexity : $$O(p U q)$$

`list.append()`

costs O(1)`list.pop()`

costs O(1)`while stack:`

depends on the number of pairs in stack.

so the time complexity is similar to space complexity.