100.Same_Tree_(Easy).md

100. Same Tree (Easy)

Date and Time: May 28, 2024 (EST)
Update: Jul 15, 2024, 22:57 (EST)

Link: https://leetcode.com/problems/same-tree/

Date	Stopwatch	Y/N	Feedback
Jun 17, 2025	11m 53s	N	first base case error

Walk-through:

For recursion version, we just want to compare if two trees' left/right subtrees are different, which are the same three conditions we check: 1. if p, q are None. 2. if p or q is None (when one node exists, but another tree's node doesn't exist). 3. if p.val != q.val.

For BFS version, we use two queues queueP, queueQ to store root's left/right nodes. If both queues are not empty, we check the same above three conditions, and add the root's left/right nodes into each queue. Finally, make sure both queues are empty so they are the same.

DFS:

# 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:
        # Run DFS on p and q at the same time, and compare values
        # dfs(p, q): if not p and not q:return. 
        # TC: O(n), n is total nodes, SC: O(1)

        def dfs(p, q):
            if not p and not q:
                return True
            if (not p or not q) or (p.val != q.val):
                return False
            return dfs(p.left, q.left) and dfs(p.right, q.right)
        return dfs(p, q)

C++

/**
 * 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) {
        /* 
        1. If not p and not q: return True
        2. If (not p or not q) or (p.val != q.val): return False
        TC: O(n), n is total nodes, SC: O(1)
        */
        if (!p && !q) {
            return true;
        } else if ((!p || !q) || (p->val != q->val)) {
            return false;
        }
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};