100. Same Tree

Intuition

The problem requires comparing two binary trees node by node. If both nodes are None, they are the same. If only one of them is None, they are not the same. If the values of the nodes are different, they are not the same. Otherwise, we need to check the left and right subtrees recursively.

Approach

1. Base Case: - If both p and q are None, return True because two empty trees are the same. - If one of p or q is None, or the values at the current nodes are different, return False.
2. Recursive Case: - Recursively check the left subtrees of p and q by calling isSameTree(p.left, q.left). - Recursively check the right subtrees of p and q by calling isSameTree(p.right, q.right). - Return True if both the left and right subtrees are the same, otherwise return False.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary trees. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).

Code

C++

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }
        if (!p || !q || p->val != q->val) {
            return false;
        } else {
            bool lSol = isSameTree(p->left, q->left);
            if (lSol) {
                return isSameTree(p->right, q->right);
            } else {
                return false;
            }
        }
    }
};

Python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        else:
            lSol = self.isSameTree(p.left, q.left)
            if lSol:
                return self.isSameTree(p.right, q.right)
            else:
                return False

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        } else {
            boolean lSol = isSameTree(p.left, q.left);
            if (lSol) {
                return isSameTree(p.right, q.right);
            } else {
                return false;
            }
        }
    }
}

JavaScript

var isSameTree = function (p, q) {
    if (!p && !q) {
        return true;
    }
    if (!q || !p || p.val != q.val) {
        return false;
    } else {
        let lSol = isSameTree(p.left, q.left);
        if (lSol) {
            return isSameTree(p.right, q.right);
        } else {
            return false;
        }
    }
};