LeetCode 100: Same Tree

Problem Restatement

We are given the roots of two binary trees:

p
q

We need to check whether the two trees are the same.

Two binary trees are the same if:

The official statement defines two binary trees as the same when they are structurally identical and their nodes have the same value. The constraints say both trees have between 0 and 100 nodes, and node values are between -10^4 and 10^4.

Input and Output

Function shape:

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

Examples

Example 1:

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

Both trees have the same shape and values:

    1
   / \
  2   3

Answer:

True

Example 2:

p = [1, 2]
q = [1, None, 2]

Tree p:

  1
 /
2

Tree q:

1
 \
  2

They contain the same values, but the structure is different.

Answer:

False

Example 3:

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

The structures match, but corresponding values differ.

Answer:

False

First Thought: Traverse Both Trees

We need to compare the trees node by node.

At each position, there are three cases:

1. Both nodes are missing.
2. One node is missing.
3. Both nodes exist.

If both nodes are missing, that position matches.

If only one node is missing, the structure differs.

If both nodes exist, their values must match, and their left and right subtrees must also match.

This naturally gives a recursive solution.

Key Insight

Two trees are the same if their roots match and their subtrees match.

So the condition is:

same(p, q) =
    p and q are both None
    or
    p.val == q.val
    and same(p.left, q.left)
    and same(p.right, q.right)

This checks structure and values at the same time.

Algorithm

Define a recursive function:

isSameTree(p, q)

At each call:

1. If both nodes are None, return True.
2. If exactly one node is None, return False.
3. If the values differ, return False.
4. Recursively compare the left children.
5. Recursively compare the right children.
6. Return True only if both subtree comparisons are true.

Walkthrough

Use:

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

Compare roots:

p.val = 1
q.val = 1

They match.

Compare left children:

p.left.val = 2
q.left.val = 2

They match.

Their children are all None, so those empty subtrees match.

Compare right children:

p.right.val = 3
q.right.val = 3

They match.

Their children are also None.

Every corresponding position matches, so return:

True

Now use:

p = [1, 2]
q = [1, None, 2]

Compare roots:

1 == 1

The roots match.

Compare left children:

p.left exists
q.left is None

One side has a node and the other side does not.

Return:

False

Correctness

The algorithm compares the two trees at corresponding positions.

If both nodes are None, then both trees are empty at that position, so that position is identical.

If exactly one node is None, then one tree has a node where the other does not, so the structures differ and the trees cannot be the same.

If both nodes exist, the algorithm first checks their values. If the values differ, the trees cannot be the same. If the values match, the trees are the same at this position only if their left subtrees are the same and their right subtrees are the same.

This is exactly the recursive definition of identical binary trees.

Therefore, the algorithm returns True exactly when the two trees have the same structure and the same values at every corresponding node.

Complexity

Let:

n = number of nodes compared
h = maximum height of the two trees

In the worst case, the trees are identical and n is the total number of nodes in either tree.

For a skewed tree, h = n.

For a balanced tree, h = O(log n).

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

        if p is None or q is None:
            return False

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

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

Code Explanation

First handle the case where both nodes are empty:

if p is None and q is None:
    return True

Then handle structural mismatch:

if p is None or q is None:
    return False

At this point, both nodes exist.

Compare their values:

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

Finally, compare both subtrees:

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

The and is important. Both the left and right subtrees must match.

Iterative BFS Implementation

We can also compare nodes level by level with a queue.

from collections import deque

class Solution:
    def isSameTree(
        self,
        p: Optional[TreeNode],
        q: Optional[TreeNode],
    ) -> bool:
        queue = deque([(p, q)])

        while queue:
            a, b = queue.popleft()

            if a is None and b is None:
                continue

            if a is None or b is None:
                return False

            if a.val != b.val:
                return False

            queue.append((a.left, b.left))
            queue.append((a.right, b.right))

        return True

This has the same O(n) time complexity.

Its space complexity is O(w), where w is the maximum width of the trees.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    p = TreeNode(1, TreeNode(2), TreeNode(3))
    q = TreeNode(1, TreeNode(2), TreeNode(3))
    assert s.isSameTree(p, q) is True

    p = TreeNode(1, TreeNode(2), None)
    q = TreeNode(1, None, TreeNode(2))
    assert s.isSameTree(p, q) is False

    p = TreeNode(1, TreeNode(2), TreeNode(1))
    q = TreeNode(1, TreeNode(1), TreeNode(2))
    assert s.isSameTree(p, q) is False

    assert s.isSameTree(None, None) is True
    assert s.isSameTree(TreeNode(1), None) is False
    assert s.isSameTree(TreeNode(1), TreeNode(1)) is True
    assert s.isSameTree(TreeNode(1), TreeNode(2)) is False

    print("all tests passed")

run_tests()

Test meaning: