## DEV Community # 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);
}
}
``````