Question about returning the right thing from recursive function (Leetcode 572)

Question

I am doing Leet Code question 572. Subtree of Another Tree:

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.

I had a working solution. However, when trying a slightly different approach, I ran into a problem with my recursive dfs function. The structure of my code is this:

def isSubTree(self, root, subRoot):
    def dfs(root, subRoot):
        # some function that returns True when certain conditions are met

    if not root: return 
        
    self.isSubtree(root.left, subRoot)
    self.isSubtree(root.right, subRoot)
    
    if root.val == subRoot.val:
        if dfs(root, subRoot):
            return True
    return False

Basically, isSubTree explores all the nodes in the tree. Once it finds a node with the same value as subRoot, it compares the sub tree rooted at that node with the sub tree rooted at subRoot with dfs().

I intended that when the dfs() function returns true, isSubTree() will also return true. If I've explored all the nodes in the tree (isSubTree() reaches the end) and dfs() hasn't returned true at all, isSubTree() will return False.

However，my code always returns false seemingly because of the last line where it returns False (I've tested it and can verify that the return True part in if dfs() was reached, also I'm pretty sure my dfs() function is correct).

My question is, is there an elegant way to have my code do what I want it to do?

Answer 1

Solved it with the following:

def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def dfs(r1, r2):
        # some function
        
        
    if not root:
        return False
        
    if root.val == subRoot.val:
        if dfs(root, subRoot):
            return True
        
    return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)