Problem Description

You are given the roots of two binary trees p and q. Your task is to determine if these two binary trees are identical.

Two binary trees are considered the same when:

1. They have the exact same structure (same shape and arrangement of nodes)
2. Every corresponding node in both trees has the same value

For example:

• If both trees are empty (null), they are the same
• If one tree is empty and the other isn't, they are different
• If both trees have nodes, each node at the same position must have the same value

The solution uses a recursive depth-first search (DFS) approach. It checks three key conditions:

1. Base case: If both nodes are null (p == q), return True since empty trees are identical
2. Mismatch detection: If only one node is null, or if both exist but have different values, return False
3. Recursive check: If the current nodes match, recursively verify that both the left subtrees are identical AND the right subtrees are identical

The algorithm traverses both trees simultaneously, comparing nodes at each position. It returns True only when all corresponding nodes throughout both trees match perfectly in both structure and value.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: Binary trees are a special type of graph where each node has at most two children and there are no cycles. The problem involves traversing and comparing two tree structures.

Is it a tree?

• Yes: The problem explicitly states we are working with binary trees. We need to compare the structure and values of two binary tree data structures.

DFS

• Conclusion: Since we're dealing with trees, the flowchart leads us directly to DFS (Depth-First Search).

The flowchart suggests using DFS for this tree problem, which makes perfect sense because:

1. We need to traverse both trees completely to ensure they are identical
2. We need to compare nodes at corresponding positions in both trees
3. DFS allows us to recursively check each subtree, comparing left with left and right with right
4. The recursive nature of DFS naturally matches the recursive structure of trees

This aligns perfectly with our solution approach where we recursively compare each node and its subtrees using DFS traversal.

Intuition

When comparing two trees to see if they're identical, think about how you would manually verify this. You'd start at the roots and check: are both roots present? Do they have the same value? Then you'd look at their children and repeat the same questions.

This naturally suggests a recursive approach. At any given pair of nodes, we need to verify three things:

1. The nodes themselves match (either both null or both have the same value)
2. Their left subtrees are identical
3. Their right subtrees are identical

The key insight is that two trees are the same if and only if their roots match AND their corresponding subtrees match. This breaks down the problem into smaller subproblems of the same type - comparing smaller trees.

Consider the edge cases first:

• If both nodes are null, they're trivially the same (empty trees are identical)
• If only one is null, they can't be the same (one exists, one doesn't)
• If both exist but have different values, they're different

Once we've handled these base cases, we can recursively apply the same logic to the children. The beauty of this approach is that each recursive call handles a smaller portion of the tree, and we only need to return True if ALL corresponding parts match.

The recursion naturally handles the tree traversal for us - we don't need to explicitly manage a stack or queue. Each function call implicitly keeps track of which nodes we're currently comparing, and the call stack ensures we visit every node pair exactly once.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The DFS recursive method provides an elegant solution to this problem. Let's walk through the implementation step by step:

Base Cases:

1. If both nodes p and q point to the same memory location (including both being null), they're identical: if p == q: return True
2. If only one node is null or the values don't match, the trees are different: if p is None or q is None or p.val != q.val: return False

Recursive Case: Once we've verified the current nodes match, we recursively check both subtrees:

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

The algorithm works by:

1. Starting at the root nodes of both trees
2. Checking if the current nodes are structurally and value-wise identical
3. If they match, recursively verifying the left subtrees are the same
4. Recursively verifying the right subtrees are the same
5. Returning True only if all checks pass

The and operator ensures both subtrees must be identical - if either recursive call returns False, the entire expression evaluates to False.

Time Complexity: O(min(m, n)) where m and n are the number of nodes in trees p and q. In the worst case (when trees are identical), we visit every node once.

Space Complexity: O(min(m, n)) for the recursion call stack. In the worst case of a skewed tree, the depth could be equal to the number of nodes.

The solution leverages the recursive nature of trees - a tree is the same as another if their roots match and their subtrees are recursively the same. This divide-and-conquer approach naturally handles all the structural comparisons needed.

Example Walkthrough

Let's walk through comparing two small binary trees to see how the recursive solution works:

Tree p:

    1
   / \
  2   3

Tree q:

    1
   / \
  2   3

Step-by-step execution:

1. Compare roots (p=1, q=1):

   • Both nodes exist ✓
   • Both have value 1 ✓
   • Proceed to check subtrees

2. Check left subtrees (p.left=2, q.left=2):

   • Both nodes exist ✓
   • Both have value 2 ✓
   • Check 2's children:
     • Left children: both null ✓ (returns True)
     • Right children: both null ✓ (returns True)
   • Node 2 comparison returns True

3. Check right subtrees (p.right=3, q.right=3):

   • Both nodes exist ✓
   • Both have value 3 ✓
   • Check 3's children:
     • Left children: both null ✓ (returns True)
     • Right children: both null ✓ (returns True)
   • Node 3 comparison returns True

4. Final result: Since root values match (1==1) AND left subtrees match (True) AND right subtrees match (True), the function returns True.

Example of trees that aren't the same:

Tree p:

    1
   / 
  2   

Tree q:

    1
     \
      2

1. Compare roots (p=1, q=1): values match ✓
2. Check left subtrees: p.left=2, q.left=null
   • One is null, one isn't ✗
   • Returns False immediately

The function returns False without checking the right subtrees since the left subtrees already differ.

Solution Implementation

Time and Space Complexity

The time complexity is O(min(m, n)), where m and n are the number of nodes in trees p and q respectively. In the worst case, when both trees are identical or differ only at the deepest leaf, we need to visit every node in the smaller tree. The algorithm terminates as soon as a mismatch is found or when we reach the end of the smaller tree, hence we visit at most min(m, n) nodes.

The space complexity is O(min(m, n)). This space is used by the recursive call stack. In the worst case, when comparing two completely unbalanced trees (like linked lists), the recursion depth can reach the height of the smaller tree. For a skewed tree, the height equals the number of nodes. In the best case of balanced trees, the space complexity would be O(log(min(m, n))), but we consider the worst case. The recursion stops when we reach the end of the smaller tree, so the maximum recursion depth is bounded by the number of nodes in the smaller tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Null Checking Order

A common mistake is checking node values before verifying both nodes exist, which leads to AttributeError when trying to access .val on a None object.

Incorrect approach:

def isSameTree(self, p, q):
    if p.val != q.val:  # Error if p or q is None!
        return False
    if p is None and q is None:
        return True
    # ... rest of the code

Correct approach:

def isSameTree(self, p, q):
    # Check for None values FIRST
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    # Now safe to access .val
    if p.val != q.val:
        return False
    # ... rest of the code

2. Using OR Instead of AND for Recursive Calls

Some developers mistakenly use or when combining the recursive results, thinking "if either subtree is the same, return True."

Incorrect approach:

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

This would incorrectly return True if only one subtree matches, even when the other differs.

Correct approach:

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

Both subtrees must be identical for the entire tree to be considered the same.

3. Forgetting to Handle the Case Where Both Nodes Exist but Have Different Values

Some implementations check for null cases but forget to compare values when both nodes exist.

Incomplete approach:

def isSameTree(self, p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    # Missing value comparison!
    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

This would incorrectly consider trees with different node values as identical if they have the same structure.

4. Comparing Node References Instead of Values

Using == to compare entire nodes instead of their values can lead to unexpected behavior.

Potentially problematic:

if p == q:  # This compares object references
    return True

While this works when both are None, it might not work as expected for non-None nodes unless they're the exact same object in memory. For clarity and correctness, explicitly check:

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