572. Subtree of Another Tree

📝 Problem Details

• Title: 572. Subtree of Another Tree
• Link: https://leetcode.com/problems/subtree-of-another-tree/
• Difficulty: Easy
• Tags/Categories: Trees DFS Recursion

💭What Were My Initial Thoughts?

- given the root of two binary trees
	- root
	- subRoot
- return true is there is a subtree of root with the same structure as node values of subRoot
- return false otherwise

💡 Explanation of Solution

1. Recursive Traversal:
	- start from the root of the main tree
	- check if it matches the subRoot
	- if not, recursively check in the left and right subtrees

2. Tree Comparison Helper (isSameTree function)
	- if both trees are nullptr, they are equal
	- if only one is nullptr, they are not equal
	- if root values differ, they are not equal
	- recursively check the left and right subtrees for equality

3. Subtree Checking (isSubtree function)
	- if the main root is nullptr, return false since there is no possible match
	- use isSameTree to check if they are identical
	- if not, recursively check root->left and root->right to see if subRoot exists there
	- return true if a match is found in any subtree

⌛ Complexity Analysis

Let n be the number of nodes in `root` and m be the number of nodes in `subRoot`. 

- The `isSameTree` function runs in O(m) time in the worst case (when two trees are identical). 
- In the worst case, we check each node of `root` to see if it matches `subRoot`. - Since there are n nodes in `root`, the worst case complexity is: 
		O(n * m) 

Space complexity: 
	- The recursive calls for `isSubtree` go as deep as O(n) in the worst case (skewed tree). 
	- The `isSameTree` function adds O(m) recursion depth. 
	- Overall, worst-case space complexity is O(n).

💻 Implementation of Solution

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