100. Same Tree

📝 Problem Details

• Title: 100. Same Tree
• Link: https://leetcode.com/problems/same-tree/
• Difficulty: Easy
• Tags/Categories: DFS

💭What Were My Initial Thoughts?

- given two trees
- write a function to check if they are the same tree or not

- DFS function that traverses the nodes of each tree simultaneously
	- if the nodes (not just the values) are equal return true
	- if the ndoes are not equal return false 

💡 Explanation of Solution

same as intuition

⌛ Complexity Analysis

Time Complexity: O(n)
- traversal of each node at most 1 time 
- if the size of p and q are different, we exit early

Space Complexity: O(log n) - O(n) depending on skew / balance of the tree

💻 Implementation of Solution

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        
        if(!p && !q) return true;  // if both nodes are null, we are at a leaf node so exit early 
        if(!p || !q) return false; // edge case where the size of the trees are different
        
        return(p->val == q->val) &&
            isSameTree(p->left, q->left) &&
            isSameTree(p->right, q->right);
    }
};