L18. Check if Two Trees are Identical or Not | C++ | Java

Determining whether two binary trees are identical is a fundamental tree-traversal problem in Data Structures and Algorithms (DSA). Two trees are considered identical if they are structurally identical and the nodes possess the same value at corresponding positions.

1. The Problem Statement: Same Tree or Not?

You are given the root nodes of two binary trees, traditionally denoted as p and q.

• Goal: Return true if tree p and tree q are identical (exact structural and value match). Return false otherwise.
• Visual Verification: If two trees have matching nodes, branches, and values down to every leaf, they are identical. If a single node differs in value or is missing in one tree while present in the other, they are not identical.

2. Core Mental Model & Intuition

The most intuitive way to verify if two trees match is to traverse both trees simultaneously.

If we walk through both trees side-by-side using any standard tree traversal technique (Pre-order, In-order, Post-order, or Level-order), every corresponding node visited at the exact same step must carry the identical value. If any mismatch occurs, or if one tree terminates earlier than the other, the trees are not identical.

3. Naive vs. Optimal Traversal Strategies

While you could technically generate linear arrays or lists of node values using a traversal and then compare the arrays element-by-element:

• Naive Array-Based Approach: Involves extra memory ($O(N)$ auxiliary space for storing traversal sequences) and requires two separate passes (one for each tree, or full collection before comparison).
• Optimal Recursive Simultaneous Traversal: Compares nodes on-the-fly during a single traversal pass. This minimizes redundant operations and allows us to short-circuit and exit early (return false) the moment a discrepancy is detected.

4. Step-by-Step Recursive Algorithm Evolution

To solve this recursively, we evaluate three primary conditions at every recursive frame:

1. Base Case 1 (Both Null): If both current nodes (p and q) are null, we have reached the end of matching branches successfully. Return true.
2. Base Case 2 (One Null, One Exists): If one node is null while the other is not, the structures diverge. Return false.
3. Value Comparison: If both nodes exist, compare their values (p.val == q.val). If they mismatch, return false.
4. Recursive Step: Recursively check both left subtrees (isSameTree(p.left, q.left)) AND right subtrees (isSameTree(p.right, q.right)). Both sub-branches must return true for the current trees to be identical.

5. Complete Flow Walkthrough

Let's trace how the recursive function evaluates two identical trees with root values 1.

6. Production Code Implementation (C++ & Java)

C++ Implementation

/**
 * 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) {
        // Base case: both nodes are null (reached end of branches)
        if (p == NULL && q == NULL) {
            return true;
        }
        
        // Base case: one node is null and the other is not
        if (p == NULL || q == NULL) {
            return false;
        }
        
        // Check if current values match, and recursively check left and right subtrees
        return (p->val == q->val) && 
               isSameTree(p->left, q->left) && 
               isSameTree(p->right, q->right);
    }
};

Java Implementation

/**
 * 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) {
        // Base case: both nodes are null
        if (p == null && q == null) {
            return true;
        }
        
        // Base case: one node is null while the other is not
        if (p == null || q == null) {
            return false;
        }
        
        // Compare values and recursively validate left and right subtrees
        return (p.val == q.val) && 
               isSameTree(p.left, q.left) && 
               isSameTree(p.right, q.right);
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Identical Definition: Two binary trees are identical if and only if they possess identical structural shapes and matching node values at every corresponding coordinate.
• Simultaneous Traversal: Comparing trees side-by-side using recursion allows for clean, concise code and early termination.
• Base Cases Matter: Always handle null pointer checks first to prevent NullPointerException (Java) or segmentation faults (C++).
• Traversal Agnostic: While Pre-order traversal is intuitive for this check, the logical structure can be validated via any traversal strategy as long as both trees are evaluated in lockstep.
• Logical Short-Circuiting: Using the logical AND (&&) operator ensures that if the left subtree check returns false, the right subtree is never unnecessarily evaluated.
• Interview Readiness: Master the base conditions and time/space complexity proofs ($O(N)$ time, $O(H)$ call stack space) for technical interviews.