# 0100. Same Tree

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Same Tree](https://leetcode.com/problems/same-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0100-same-tree)

Given the roots of two binary trees `p` and `q`, 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.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in both trees is in the range `[0, 100]`.
* `-10^4 <= Node.val <= 10^4`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
We could check two trees are identical by different kinds of traversal.\
For here, we use **pre-order traversal**.
{% endhint %}

Instead of iterating two trees separately, we could **traverse two trees simultaneously**. However, we should take care of t**he existence of child nodes** while traversing.

* If two nodes popped from the stack are **both null, skip the current iteration.**
* If **one of the nodes** popped from the stack is **null, return False.**
* If **both** nodes popped from the stack **are not null, check their values.**

Last, append two nodes' left- and right-nodes onto the stack for the next iteration.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # (base case)
        if not p and not q: return True
        if not p or  not q: return False
        if p.val != q.val: return False
        
        # ==================================================
        #  Tree + DFS                         (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n) for worst case, O(log(n)) for avg case
        
        stack = [(p,q)]
        while stack:
            node1, node2 = stack.pop()
            
            if not node1 and not node2: continue
            
            if (node1 and not node2) or (not node1 and node2): return False
            if (node1 and node2) and node1.val != node2.val: return False
            
            stack.append((node1.left,  node2.left))
            stack.append((node1.right, node2.right))
            
        return True
    
        '''
        # ==================================================
        #  Tree + DFS                         (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n) for worst case, O(log(n)) for avg case
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        /* base case */
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
```

{% endtab %}
{% endtabs %}