Same Tree Problem

Problem Statement

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.

LeetCode:

• Same Tree

Constraints:

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

Examples

Example 1:

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

Tree p:
     1
    / \
   2   3

Tree q:
     1
    / \
   2   3

Output:true

Explanation: As both trees are identical in structure and node values.

Example 2:

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

Tree p:
     1
    /
   2

Tree q:
    1
     \
      2

Output: false

Explanation:
The structure of both the trees are different

Example 3:

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

Tree p:
      1
     / \
    2   1

Tree q:
      1
     / \
    1   2

Output: false

Explanation:
The structure is same for both the trees but values are different.

Different Approaches

1️⃣ Recursive Approach

Intuition:

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.

Code Implementation:

#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.

Complexity Analysis

• 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:

Intuition:

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:

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:

• 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.