100. Same Tree

Problem Statement:

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].
• -104 <= Node.val <= 104

Solution:

Algorithm:

1. If both the trees are empty, return true.
2. If both the trees are not empty, then check if the root node of both the trees are same.
3. If the root node of both the trees are same, then recursively check for the left and right subtree of both the trees.
4. If the root node of both the trees are not same, then return false.
5. If the left subtree of both the trees are not same, then return false.
6. If the right subtree of both the trees are not same, then return false.
7. If all the above conditions are satisfied, then return true.

Code:

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

}

Time Complexity:
O(n)

Space Complexity:
O(n)