Same Tree easy

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

Steps

  1. Base Case: If both p and q are null, they are the same, so return true. If one is null and the other is not, they are different, so return false.

  2. Value Check: Compare the values of the root nodes p.val and q.val. If they are different, return false.

  3. Recursive Calls: Recursively call the isSameTree function on the left subtrees (p.left, q.left) and the right subtrees (p.right, q.right). Both recursive calls must return true for the trees to be the same.

Explanation

The solution uses a recursive approach to compare the trees. The base case handles the scenario where one or both trees are empty. The value check ensures that the root nodes have the same value. The recursive calls efficiently traverse both trees simultaneously, ensuring that the structure and values at each level match. If at any point a mismatch is found (different values or differing structure due to null nodes), the function immediately returns false. Otherwise, it proceeds recursively until the entire trees have been compared.

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) {
        //Base Case: Both null, they are same
        if(p == null && q == null) return true;
        //Base Case: One null, other not null, they are different
        if(p == null || q == null) return false;

        //Check if root values are same
        if(p.val != q.val) return false;
        
        //Recursive calls on left and right subtrees.  Both must be true
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In the best case (a balanced tree), H would be logâ‚‚N.