# Leetcode 100. 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.

**Example 1:**

`Input: p = [1,2,3], q = [1,2,3]`

Output: true

**Example 2:**

`Input: p = [1,2], q = [1,null,2]`

Output: false

**Example 3:**

`Input: p = [1,2,1], q = [1,1,2]`

Output: false

**Constraints:**

- The number of nodes in both trees is in the range
`[0, 100]`

. `-10^4 <= Node.val <= 10^4`

# Intuition

We just need to traverse both trees and check whether each of the values of the trees is properly matching. So any type of tree traversal will be sufficient.

# Approach

We will be doing recursively(Preorder traversal)

- Check the base conditions :

-> Check whether both the trees are null, if yes return true.

-> Check whether any of the trees is null, if yes then return false as they are not the same. - Check whether the current values at the 2 trees are equal, if yes return true.
- Continue iteration recursively on the left and right subtree.

# Complexity

- Time complexity:

We are traversing the whole tree. So if there are n number of trees, then the time complexity will be O(n). - Space complexity:

Space complexity will be O(H) where H = height of the tree

# Code

`/**`

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

* }

*/

class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

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);

}

}