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

1. 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.
2. Check whether the current values at the 2 trees are equal, if yes return true.
3. 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);    }}`