C++: Subtree of Another Tree

Thought Process

The problem requires checking if the 'subRoot' tree is a subtree of the root tree or not. To solve this, we use a helper function 'areSameTree' to check if two trees are identical. We then recursively check if the 'subRoot' matches any subtree of the root. If a match is found, we return true; otherwise, we return false. 

/**
 * 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 areSameTree(TreeNode *root, TreeNode *subRoot){

        if(root == NULL && subRoot == NULL)
            return true;
        else if(root == NULL || subRoot==NULL)
            return false;
            
        if(root->val == subRoot->val)
            return areSameTree(root->right,subRoot->right) && areSameTree(root->left,subRoot->left);
        else
            return false;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        
        if(root == NULL && subRoot == NULL)
            return true;

        else if(root == NULL || subRoot == NULL)
            return false;

        // If both are same tree then return true
        if(areSameTree(root,subRoot))
            return true;
        else  // Else try matching with left & right subtrees of root node.
            return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
    }
};

Code Complexity

Time Complexity: O(n * m)

The algorithm checks each node of the root tree against the subRoot tree, where 'n' is the number of nodes in the root tree and 'm' is the number of nodes in the subRoot tree.

Space Complexity: O(h)

The algorithm uses recursion, and the space complexity depends on the height h of the root tree due to the call stack.

Code copied!