Same Tree | Leetcode 100 | Recursive Solution Explained in Detail

You are given two binary trees p and q. You need to check if the two trees are the same.

Two binary trees are considered the same if:

1. They are structurally identical (same shape).
2. Their corresponding nodes have the same value.

Here’s the [Problem Link] to begin with.

Examples

Example 1

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

    p:         1        q:        1
              / \                / \
             2   3              2   3

Output: true

Example 2

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

    p:         1        q:      1
              /                  \
             2                    2

Output: false

Example 3

Input: p = [1,2,1], q = [1,1,2]

    p:         1        q:        1
              / \                / \
             2   1              1   2

Output: false

Intuition and Approach

The problem is a straightforward recursive tree comparison:

1. Base case:
   • If either node is None, both must be None to be considered equal. If one is None and the other isn’t, the trees differ.
2. Check values:
   • If both nodes exist but their values differ, return False.
3. Recursive step:
   • Recursively check if the left subtrees are identical.
   • Recursively check if the right subtrees are identical.
4. Combine results:
   • Only if both left and right subtrees are the same do we return True.

Code Implementation

class Solution:
    def solve(self, node1, node2):
        if node1 is None or node2 is None:
            return node1 == node2
        if node1.val != node2.val:
            return False
        leftSide = self.solve(node1.left, node2.left)
        if leftSide == False:
            return False
        rightSide = self.solve(node1.right, node2.right)
        if rightSide == False:
            return False
        return leftSide and rightSide

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return self.solve(p, q)

Code Explanation

• Line 1: If either node is None, return whether they are both None. This neatly handles empty subtrees.
• Line 2: If both nodes exist but values differ, return False.
• Recursive checks:
  • Compare left subtrees with solve(node1.left, node2.left).
  • If the result is False, return immediately (early exit).
  • Compare right subtrees similarly.
• Final return: If both left and right checks are True, the current subtree is identical.

The isSameTree method simply starts the recursion from the root nodes p and q.

Time and Space Complexity

• Time Complexity:
  Each node in both trees is visited once, so O(N) where N is the number of nodes (assuming both trees have similar size).
• Space Complexity:
  Space comes from the recursion stack. In the worst case (completely skewed tree), the depth is O(N).
  For balanced trees, recursion depth is O(log N).

Conclusion

The Same Tree problem is a clean example of recursive tree traversal. By comparing node values and recursively checking left and right subtrees, we can determine structural and value equality in O(N) time.

This recursive solution is elegant and easy to understand, but it can also be implemented iteratively using BFS/DFS with a queue or stack.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.