How does this statement work under the hood? -> "Recursive call 1 OR Recursive call 2"

Question

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        return self.helper(root,set(),k)
    
    
    def helper(self,node,container,k):
        if node is None:
            return False
        
        if (k - node.val) in container:
            return True
        
        container.add(node.val)
        
        return self.helper(node.left,container,k) or self.helper(node.right,container,k)

Context about the Code - This is from Leetcode problem 653. Two Sum IV - Input is a BST.

Problem Description: We are supposed to find two nodes which sum up to k:inp, if any such node exists we return BOOL -True else: False

    return self.helper(node.left,container,k) or self.helper(node.right,container,k)

Can someone help how this above line of code is working in the background, as in, will the left - subtree call will be executed completely before moving to the right subtree traversal (on the right of OR operator) or is it that both the subtrees are traversed at the same time simultaneously with the OR operator.

Also won't there be two sub-sets created for for every left and right subtree when they are called and if so they're created, how is the code checking in on the other subset present in other half of the tree if there's a compliment present in that other half of the recursive call. Very confused, help appreciated.

Answer 1

Python will do short circuit evaluation for the or statement.

return self.helper(node.left,container,k) or self.helper(node.right,container,k)

Here:

self.helper(node.left,container,k)

is evaluated first, this is a recursive call.

If the return value from this call is True then the whole expression is short-circuited & the or-expression returns True - the right subtree is never searched (that recursive call never happened)

If the return value is False, then the other side of the or is also evaluated - the search in the right subtree - and the complete expression is evaluated based on it's result.

Answer 2

In python (and most computer languages), boolean operations are called "lazy" (or short-circuiting)

This means they first execute the first operand, and if that is enough to know the result, they will skip the second one. [1]

This is to be compared to normal operators such as + that always excute both operands first

For example, when the interpreter reads

a() + b()

it will first excute a(), then b() then the + operator (ie the __add__ function), and return the result.

But on the contrary, when it reads

a() or b()

it will first execute a(). If a() returns True, then the interpreter knows the result is going to be True. Thus it will skip executing b(). Otherwise it will return the value of b().

Thus, in your specific case,

return self.helper(node.left,container,k) or self.helper(node.right,container,k)

is equivalent to

temp =  self.helper(node.left,container,k)
if temp:
   return temp
else:
   return self.helper(node.right,container,k)

So, to answer the initial question, the left tree is always traveled first. Then if the item was found in the left tree, the right tree is not traversed. Otherwise the right tree is searched.

[1]: from the doc

The expression x or y first evaluates x; if x is true, its value is returned; otherwise, y is evaluated and the resulting value is returned.