Leetcode 100. Same Tree

Photo by Marita Kavelashvili on Unsplash

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:

From Leetcode

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

From Leetcode

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

From Leetcode

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