Problem

Given the roots of two binary trees p and q, determine whether they are exactly the same.

Two binary trees are considered the same if:

  • They have the same structure
  • Every corresponding node contains the same value

For example:

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

Output:
true
Input:
p = [4,7]
q = [4,null,7]

Output:
false

Although both trees contain the values 4 and 7, their structures differ, so they are not the same.

Intuition

At every pair of nodes, we need to answer three questions:

  1. Are both nodes missing?
  2. Is one node missing while the other exists?
  3. If both exist, do they have the same value?

If the current pair of nodes passes these checks, we simply repeat the exact same process for their children.

Notice that this problem naturally breaks itself into two identical subproblems:

  • Compare the left subtrees.
  • Compare the right subtrees.

This makes recursion a perfect fit.

Recursive DFS Solution

from typing import Optional

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True

        if not p or not q:
            return False

        if p.val != q.val:
            return False

        return (
            self.isSameTree(p.left, q.left)
            and
            self.isSameTree(p.right, q.right)
        )

Step-by-Step

Suppose we compare these trees:

    1              1
   / \            / \
  2   3          2   3

We begin at the roots.

1 == 1 ✓

Now compare the left children.

2 == 2 ✓

Both left children have no children, so every recursive call returns True.

Next compare the right children.

3 == 3 ✓

Again, both children are identical.

Since both the left comparison and the right comparison return True, the original call also returns True.

Now consider:

    1              1
   /                \
  2                  2

The first comparison succeeds.

1 == 1 ✓

Then we compare the left children.

2 vs None

One node exists while the other doesn't.

Immediately we return:

False

There's no need to continue checking the rest of the tree.

Why the Base Cases Matter

Case 1: Both nodes are None

if not p and not q:
    return True

If we've reached the end of both trees simultaneously, everything matched up to this point.

None    None

These are considered equal.

Case 2: Only one node exists

if not p or not q:
    return False

Examples:

2      None

or

None      2

The structures differ, so the trees cannot be identical.

Case 3: Values differ

if p.val != q.val:
    return False

Example:

5      8

Even though the structure matches, the node values do not.

Why We Use and

The trees are only identical if:

  • the left subtrees are identical
  • and
  • the right subtrees are identical
return (
    self.isSameTree(p.left, q.left)
    and
    self.isSameTree(p.right, q.right)
)

Think of it like this:

Same Tree?

Left matches?   True
Right matches?  True

Result = True AND True
       = True

But if either side fails:

Left matches?   False
Right matches?  True

Result = False

One mismatch anywhere in the tree means the trees are different.

A Slightly Shorter Version

The same logic can be written a little more compactly:

class Solution:
    def isSameTree(self, p, q):
        if not p and not q:
            return True

        if p and q and p.val == q.val:
            return (
                self.isSameTree(p.left, q.left)
                and
                self.isSameTree(p.right, q.right)
            )

        return False

This combines several checks into a single condition:

  • Both nodes exist.
  • Their values match.

Otherwise, return False.

Functionally, it is identical to the previous solution.

Complexity Analysis

Time Complexity

O(n)

Every pair of corresponding nodes is visited exactly once.

Space Complexity

O(h)

Where h is the height of the tree due to the recursive call stack.

  • Balanced tree: O(log n)
  • Skewed tree: O(n)

Interview Expectations

For this problem, the recursive DFS solution is the standard interview solution.

Interviewers are mainly looking for whether you correctly handle the three key cases:

  1. Both nodes are None.
  2. One node is None.
  3. Both nodes exist but their values differ.

Once those cases are handled, recursively comparing the left and right subtrees is straightforward.

An iterative solution using a queue or stack is also valid and demonstrates familiarity with tree traversals, but it is not generally expected unless the interviewer specifically asks for a non-recursive approach.

Key Takeaways

  • Compare two nodes at a time.
  • Handle the three base cases before recursing.
  • Both left and right subtrees must match.
  • Recursion mirrors the recursive structure of a binary tree, making it the cleanest solution.
  • The recursive DFS solution runs in O(n) time and O(h) space, which is optimal for this problem.