why the simple DFS recursion works?

Question

For leetcode 112, the question asks you to find if there exists a path from root to leaf that their value add up to targetSum, the solution goes like this:

class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: bool
        """
        
        if not root: return False
        
        if not root.left and not root.right:
            return root.val == targetSum
        
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

And I can't wrap my head around why the last line inside the function breaks the recursion and returns the final True but if it's False it continues back to the DFS search.

In `X() or Y()`, `Y` is never called if `X()` returns a truthy value. — chepner, Aug 02 '22 at 16:55

score 3 · Answer 1 · answered Aug 02 '22 at 17:00

3

or short-circuits, so the return statement is just a short version of

t = self.hasPathSum(root.left, targetSum - root.val)
if t:
    return t
return self.hasPathSum(root.right, targetSum - root.val)

answered Aug 02 '22 at 17:00

chepner

497,756
71
530
681

score 2 · Answer 2 · answered Aug 02 '22 at 17:01

but if it's False it continues back to the DFS search

This might be where you're getting lost. It doesn't really do two separate things: both options in the return statement execute a DFS. What this statement is saying is if you are at a leaf, which is written here:

if not root.left and not root.right:
        return root.val == targetSum

then if any path leads to the targetSum, return True, all other options return False. This is able to exit early if the answer is found when searching the left branch (as the code will return True there and never search the right branch) but the recursion always just ends at one of the two base cases:

if not root: return False

and

if not root.left and not root.right:
    return root.val == targetSum

flyby · Answer 3 · 2022-08-02T17:14:53.587

0

The recursion happen for both left and right side exhaustively (completely). Nothing breaks.

The final result is the OR operation of both left and right sides.

Edit: In python the second argument will be evaluated only if the first is false. (please check Gassa's comment)

edited Aug 02 '22 at 17:14

answered Aug 02 '22 at 17:02

flyby

136
6

1

Wrong, see here: https://stackoverflow.com/q/2580136 – Gassa Aug 02 '22 at 17:07
1

I was thinking in terms of the algorithm but yes python does not check if anymore if first argument is true. Didn't know it was called short circuit. Thanks! – flyby Aug 02 '22 at 17:12

why the simple DFS recursion works?

3 Answers3