Home > database >  How does this recursive function with two different return types work?
How does this recursive function with two different return types work?

Time:07-15

This function below finds the instructions to get to a specified node in a binary tree ("L"= left, "R"= right).

 def find(n: TreeNode, val: int, path: List[str]) -> bool:
            if n.val == val:
                return True
            if n.left and find(n.left, val, path):
                path  = "L"
            elif n.right and find(n.right, val, path):
                path  = "R"
            return path

I see that the base case returns True to finish the loop and also to tell preceding recursive calls that the path they're on will eventually reach the val node, but I don't understand where return path fits into all of this.

  1. How does returning two different types of objects (boolean and List[str]) work in this recursive function?
  2. Why are we returning path at all? Removing that line does give me the wrong answer, but I don't see anywhere where the return value is set to a variable to be used somehow.

CodePudding user response:

A1. The "-> bool" is called Python type hint. Python type hints are not used at runtime. In fact, by the time your program runs, all the type information you’ve provided has been erased. In another word, Python doesn't care type. You can learn more about Python type hint from here.

A2-1. The path variable holds the search path. When the path in the top level find is returned, you will get the full search path.

A2-2 The function in Python will returns None if no return in it. For example:

def foo():
    print("hello")

the foo returns None, same as foo2 below

def foo2():
    print("hello")
    return None
  • Related