1. Understanding the Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

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

The Core Challenge:

You cannot just compare the raw memory addresses of the objects, nor can you rely on a simple in-order traversal (since different tree structures can yield the same in-order sequence). You must verify both structure and values simultaneously.

2. The Naive Approach: Serialization (Array Comparison)

An intuitive, albeit heavier, way to handle this problem is to traverse both trees entirely (using Pre-order or Level-order traversal), record their values (including null markers for missing children) into two separate arrays, and then simply check if array_p == array_q.

Trade-off Analysis

While this logic works and is conceptually simple, it is highly inefficient in practice:

• Time Complexity: O(N + M) — It forces a full traversal of both trees even if the root nodes immediately mismatch.
• Space Complexity: O(N + M) — Storing the entirety of both trees in dynamic arrays creates unnecessary memory overhead.

3. The Optimal Approach: Recursive DFS (O(N) Time, O(H) Space)

To pass a senior-level technical interview, we want to achieve an elegant, single-pass evaluation that short-circuits (stops executing) the moment a mismatch is found, without allocating massive arrays.

We can achieve this using Depth-First Search (DFS) to traverse both trees synchronously. At any given pair of nodes, we only need to check three things:

• If both nodes are null, this branch is valid and identical. We return true.
• If only one node is null, or if both nodes exist but their values do not match, the trees are different. We return false.
• If the current nodes match, we recursively check if their left subtrees are the same AND their right subtrees are the same.

This single observation completely unifies the logic, replacing heavy array serialization with a concise recurrence relation!

4. The Logic Step-by-Step

1. Base Case (Success): Check if both p and q are null. If so, return true.
2. Base Case (Failure): Check if only one of them is null (e.g., not p or not q). Since we already checked if both are null, reaching this means they are structurally different. Return false.
3. Value Check: Check if p.val != q.val. If the values differ, return false.
4. Recursive Step: Call the function recursively for the left children (p.left, q.left) and the right children (p.right, q.right).
5. Combine: Return the logical AND of the left and right recursive calls. Both sides must be identical for the whole tree to be identical.

5. Complexity Analysis

• Time Complexity: O(min(N, M)) — Where N and M are the number of nodes in trees p and q. Because the algorithm short-circuits upon the first mismatch, in the worst case (where trees are identical) it visits every node once.
• Space Complexity: O(min(H1, H2)) — Where H1 and H2 are the heights of the trees. This represents the maximum depth of the recursion stack. In a perfectly balanced tree, this is O(log N). In a completely skewed tree (a linked list), this degrades to O(N).

6. Code Implementations

Expand the sections below to see the optimal recursive Depth-First Search implementations across different languages.

# 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:
        # Both nodes are null: identical structure here
        if not p and not q:
            return True
        
        # One is null or values don't match: not identical
        if not p or not q or p.val != q.val:
            return False
        
        # Recursively verify both left and right subtrees
        return self.isSameTree(p.left, q.left) and \
               self.isSameTree(p.right, q.right)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Both nodes are null: identical structure here
        if (p == null && q == null) {
            return true;
        }
        
        // One is null or values don't match: not identical
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        
        // Recursively verify both left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Both nodes are null: identical structure here
        if (!p && !q) {
            return true;
        }
        
        // One is null or values don't match: not identical
        if (!p || !q || p->val != q->val) {
            return false;
        }
        
        // Recursively verify both left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the "Same Tree" recursive pattern! The key takeaway from this problem is discovering how to traverse two independent data structures simultaneously. By leveraging the call stack and evaluating early failure conditions (not p or not q), you converted an exhaustive serialization approach into an elegant, highly-optimized DFS traversal. Keep this simultaneous traversal technique in your mental toolkit, as it is the exact foundation for advanced tree problems like Symmetric Tree, Subtree of Another Tree, and tree merging questions!