is there a better way to exit the recursion?

Question

I have this function:

class Solution:
def __init__(self):
        self.flag = False


def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
    curr_sum = 0            

    
    def dfs(root, curr_sum, target_sum=targetSum):
        if self.flag == True:
            return True
        if root == None:
            return 0
        print(root.val)
        curr_sum += root.val
        print(curr_sum)
        if curr_sum == target_sum:
            self.flag = True
        dfs(root.left, curr_sum)
        dfs(root.right, curr_sum)
    dfs(root, curr_sum, targetSum)
    if self.flag == True:
        return True
    return False

When tree has root-to-leaf path which sum equals to target_sum, I want to end recursion and get True. I managed to do that by adding dunder method init and setting there flag to False, which I switch when requirements are met. But it feels kind of not clean and not beautiful in my opinion. How should I do it in a more clean manner?

Answer 1

You don't need a Solution class at all (forcing everything to be a class is a Java-ism that you don't need in Python code), and your function should return its value rather than sticking it in an external variable.

The general pattern for a recursive function is:

• check base case, return the solution immediately if it's met
• otherwise, return the result of calling the function again with modified arguments that get you closer to a base case.

def has_path_sum(self, root: TreeNode, target_sum: int) -> bool:
    """Returns whether any path through the tree 
    has values that sum to *exactly* target_sum."""
    def dfs(node: TreeNode, curr_sum: int) -> bool:
        """DFS helper that tracks sum of all nodes traversed."""
        # Base case: return False if we run out of nodes.
        if node is None:
            return False
        curr_sum += node.val
        return (
            # Base case: return True if we hit the target sum.
            curr_sum == target_sum
            # Otherwise, recurse into left and right subtrees.
            or dfs(node.left, curr_sum)
            or dfs(node.right, curr_sum)
        )

    return dfs(root, 0)

Note the use of or in the last part of the DFS helper -- an or immediately returns once either of its clauses is True (in order), so this:

        return (
            # Base case: return True if we hit the target sum.
            curr_sum == target_sum
            # Otherwise, recurse into left and right subtrees.
            or dfs(node.left, curr_sum)
            or dfs(node.right, curr_sum)
        )

is just a nicer/shorter way of saying this:

        # Base case: return True if we hit the target sum.
        if curr_sum == target_sum:
            return  True
        # Otherwise, recurse into left and right subtrees.
        elif dfs(node.left, curr_sum):
            return True
        elif dfs(node.right, curr_sum):
            return True
        else:
            return False