Problem Statement

Given two binary trees, write a function to check if they are structurally identical and have the same node values.

Examples

Example 1:

Consider two binary trees:

Tree 1:
     1
    / \
   2   3

Tree 2:
     1
    / \
   2   3

The function should return true since both trees are identical in structure and node values.

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

Output: true

Different Approaches

1 Recursive Approach:

1. Traverse both trees simultaneously.
2. At each step, compare the current nodes' values and
3. recursively check their left and right subtrees.
4. If at any point, the values are not equal or the structures differ, return false.
5. If both trees are fully traversed and no differences are found, return true.

2 Iterative Approach using Stack

1. Perform iterative preorder traversal on both trees using stacks.
2. At each step, compare the current nodes' values and push their children onto the stack.
3. If the values are not equal or one tree has a child while the other does not, return false.
4. If both stacks are empty and no differences are found, return true.

Code Implementation

1 Recursive:

#include <iostream>
#include <stack>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true; // Both trees are empty
        if (!p || !q) return false; // One tree is empty, the other is not
        if (p->val != q->val) return false; // Nodes have different values
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); // Recursively check left and right subtrees
    }
};

int main() {
    Solution solution;
    
    // Example usage
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);

    TreeNode* tree2 = new TreeNode(1);
    tree2->left = new TreeNode(2);
    tree2->right = new TreeNode(3);

    cout << "Are the trees the same? " << (solution.isSameTree(tree1, tree2) ? "Yes" : "No") << endl;

    return 0;
}

Explanation:

• If both p and q are NULL, indicating empty trees, we return true as they are considered identical.
• If one of p or q is NULL while the other is not, the trees are structurally different, so we return false.
• If the values of the current nodes p and q are different, the trees cannot be identical, so we return false.
• Otherwise, we recursively call isSameTree for the left and right subtrees of both p and q. If both recursive calls return true, indicating that the corresponding subtrees are identical, we return true; otherwise, we return false.

2 Iterative Approach using Stack:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> stackP, stackQ;
        stackP.push(p);
        stackQ.push(q);
        
        while (!stackP.empty() && !stackQ.empty()) {
            TreeNode* nodeP = stackP.top();
            TreeNode* nodeQ = stackQ.top();
            stackP.pop();
            stackQ.pop();
            
            if (!nodeP && !nodeQ) continue; // Both nodes are empty, continue to next iteration
            if (!nodeP || !nodeQ || nodeP->val != nodeQ->val) return false; // Nodes are not identical
            stackP.push(nodeP->right); // Push right children onto stack
            stackP.push(nodeP->left); // Push left children onto stack
            stackQ.push(nodeQ->right); // Push right children onto stack
            stackQ.push(nodeQ->left); // Push left children onto stack
        }
        
        return stackP.empty() && stackQ.empty(); // Both stacks should be empty for trees to be identical
    }
};

Explanation:

1. We define a class Solution containing the function isSameTree, which takes pointers to the root nodes of two binary trees (p and q) as arguments.
2. We use two stacks (stackP and stackQ) to perform iterative preorder traversal simultaneously on both trees.
3. We push the root nodes of both trees onto their respective stacks to initiate traversal.
4. While both stacks are not empty:
   1. Pop the top nodes (nodeP and nodeQ) from both stacks.
   2. If both nodes are empty, continue to the next iteration.
   3. If one node is empty while the other is not, or their values are not equal, return false.
   4. Push the right and left children of both nodes onto their respective stacks for traversal.
5. After the traversal is complete, both stacks should be empty for the trees to be identical.

Complexity Analysis

1 Recursive Approach:

• Time Complexity: O(n), where n is the number of nodes in the smaller tree.
• Space Complexity: O(h), where h is the height of the tree due to recursive calls on the stack.

2 Iterative Approach using Stack:

• Time Complexity: O(n), where n is the number of nodes in the smaller tree.
• Space Complexity: O(h), where h is the height of the tree due to the stack space used for traversal.