Same Tree

Problem Description

Given the roots of two binary trees p and q, check if they are the same.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same values.

Examples

Constraints

• The number of nodes in both trees is in the range [0, 100].
• -10⁴ ≤ Node.val ≤ 10⁴

Verifying Structure and Value at Every Node

To verify that two trees are identical, you must confirm that every corresponding pair of nodes matches. At any step in the comparison:

• If both nodes are null, this branch is identical (returns true).
• If only one node is null, the structures differ (returns false).
• If the values of the nodes do not match, they are not identical (returns false).

If the current nodes match in structure and value, you recursively verify that their left subtrees are identical, and that their right subtrees are identical. The trees are identical only if both child comparisons succeed.

Solution 1: Recursive Depth-First Search

Use a simple recursive pre-order traversal to compare nodes.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // both nodes are null: structural match
        if (p == null && q == null) return true;
        // only one node is null: structural mismatch
        if (p == null || q == null) return false;
        // value mismatch
        if (p.val != q.val) return false;

        // compare subtrees recursively
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # both nodes are null: structural match
        if not p and not q:
            return True
        # only one node is null: structural mismatch
        if not p or not q:
            return False
        # value mismatch
        if p.val != q.val:
            return False

        # compare subtrees recursively
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // both nodes are null: structural match
        if (!p && !q) return true;
        // only one node is null: structural mismatch
        if (!p || !q) return false;
        // value mismatch
        if (p->val != q->val) return false;

        // compare subtrees recursively
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Complexity Analysis:

• Time Complexity: O(min(n, m)) where n and m are the number of nodes in tree p and q. We stop as soon as we find a mismatch.
• Space Complexity: O(min(h1, h2)) where h1 and h2 are the heights of the trees, representing the recursive call stack depth.

Where it breaks: On deeply skewed linear trees, the recursive call stack scales linearly with height, which can cause stack overflows in memory-restricted runtimes.

Common Mistakes

• Forgetting to check the null conditions first. If you check p.val == q.val before confirming that p and q are non-null, you will trigger null pointer exceptions.
• Short-circuiting the structural check incorrectly. Writing if (p == null || q == null) return false works only if the preceding if (p == null && q == null) return true check is executed first.
• Returning the structural match status without comparing the child nodes recursively. Checking only the root values does not verify the subtrees.

Frequently Asked Questions

Can we solve this using an iterative BFS traversal? Yes. You can use a queue and push nodes from both trees in pairs: [p, q]. At each step, pop the pair, verify matching values and structure, then push their children in pairs: [p.left, q.left] and [p.right, q.right].

What if the node values can contain nulls? According to the LeetCode definition, tree nodes store integer values, which are primitive types or non-null wrapper values. Structure null checks handle missing nodes.

What does this problem test in interviews? It tests your ability to translate logical definitions (identical trees) into clean base cases and recursive steps while avoiding null pointer errors.

← All Problems