LeetCode: 572. Subtree of Another Tree

The Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Example

Input:  [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    return  isSameTree(root, subRoot) ||
    (root != nullptr && 
        (
	        isSubtree(root->left, subRoot) || 
	        isSubtree(root->right, subRoot)
        )
    );
}

bool isSameTree( TreeNode *root, TreeNode *sub ) {

    if ( root == nullptr ) return sub == nullptr;
    else if ( sub == nullptr ) return false;

    return  root->val == sub->val &&
    		isSameTree( root->left, sub->left ) &&
    		isSameTree( root->right, sub->right );

}

Let's break down the code step by step:

Function Definitions:

• isSubtree(TreeNode* root, TreeNode* subRoot): This function checks if a binary tree named subRoot is a subtree of another binary tree named root.
• isSameTree(TreeNode* root, TreeNode* sub): This function checks if two binary trees, one named root and the other sub, are exactly the same.

isSameTree Function:

• This function is used to compare two binary trees, checking if they are exactly the same in structure and node values.
• It takes in two parameters, root and sub, which are the roots of the two binary trees being compared.
• If root is nullptr (i.e., the tree is empty), the function returns true if sub is also nullptr, indicating both trees are empty. If sub is not nullptr, it means the trees are not the same.
• If sub is nullptr, it means we are comparing a non-empty tree (root) with an empty tree (sub), so the function returns false.
• Finally, the function compares the node values of the current nodes in both trees (root->val and sub->val). If the values are the same, it recursively calls itself on the left and right subtrees of both trees (root->left, sub->left, root->right, and sub->right), effectively checking each corresponding pair of nodes in both trees.

isSubtree Function:

• This function is used to check if one binary tree (named subRoot) is a subtree of another binary tree (named root).
• It first checks if subRoot is exactly the same as root using the isSameTree function. If they are the same, then subRoot is indeed a subtree of root.
• If subRoot is not the same as root, the function proceeds to check if subRoot is a subtree of the left subtree of root or the right subtree of root.
• It does this by recursively calling itself on both the left and right subtrees of root and checking if either of them contains subRoot.