Problem 19 - Same Tree

Explore our archive for previous posts.

Question

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].

• -10000 <= Node.val <= 10000

Approach

In this solution, we use a recursive approach to determine whether two binary trees p and q are identical.

The isSameTree method takes two TreeNode parameters, p and q, representing the roots of the respective trees. It returns a boolean value indicating whether the trees are the same or not.

The solution follows these steps:

1. Base case: If both p and q are null, it means we have reached the end of both trees, and they are considered equal. So, we return true.

2. Check if either p or q is null, or if their values are different. If any of these conditions are true, it means the trees are not the same, so we return false.

3. Recursively call the isSameTree method for the left subtrees (p.left and q.left) and the right subtrees (p.right and q.right). If both recursive calls return true, it means the left and right subtrees are the same. In that case, we can conclude that the trees are the same, and we return true.

Solution

Solve it here

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Base case: Both nodes are null, so they are considered equal
        if (p == null && q == null) {
            return true;
        }
        
        // Check if either node is null or their values are different
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        
        // Recursively check the left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(n), where n is the total number of nodes in the binary trees. This is because in the worst case, we need to visit every node in both trees to compare their values.

Space Complexity: The space complexity is O(h), where h is the height of the trees. In the recursive calls, the space required for the call stack is proportional to the height of the trees. In the worst case, if the trees are skewed and have a height of n, the space complexity becomes O(n). However, in the average case, the space complexity is O(log n) for balanced trees.