Congratulations on successfully implementing the recursive DFS algorithm! This is no small feat despite the small amount of code we’ve written so far, but we aren’t finished yet. So far, our method only returns a TreeNode object with a value matching our target, but we also want to know the path from the root to the discovered node.
Now we’re going to make modifications to our function to support finding the path. We’ll represent the path as an ordered collection of TreeNode objects, with the root in the initial position and the found target node at the end. To keep things simple, if no match is found, we’ll return None.
Instructions
The first thing we need to do is extend our function to accept the path as a variable. This way we can maintain the path by passing the current search path to the recursive call, and adding the current node to the end of the current path before checking for value equality.
Start by adding a third parameter, path, to the dfs() function. Give this parameter a default value of an empty tuple.
We could use a list here, but we need to be very careful when passing mutable objects as inputs to functions, especially in a recursive function like this one.
Now we need to update the path to include the current node. Let’s insert a new line at the beginning of dfs() that sets path to a new tuple which has been created by adding the current path tuple to a tuple with just the root.
Now that we’re updating our path to include the current root node, we need to pass the current path into the recursive calls. If we don’t include the path in the call, the default value of the empty tuple will be used and we’ll lose the path we’ve built up thus far.
Add the path variable to the recursive dfs() call.