# Same Tree

## Problem

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

{% hint style="info" %}
For example:

```
Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true
```

```
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false
```

{% endhint %}

## Solution

```
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and \
               self.isSameTree(p.right, q.right)
               
  #Time: O(N)
  #Space: O(log n)
```