Now we have a recursive DFS function that also keeps track of the path as we search, but there’s one thing still remaining. We need to return the path! Let’s update our function one last time to output the path and complete our DFS algorithm.
We could modify our function to return the path in multiple ways. One simple thing we could do is have our function return a tuple of
(found TreeNode, path tuple of TreeNodes). However, we know that the found TreeNode is always the last item of our path, so returning this object along with the path is redundant.
Instead, let’s change the method to only return the path. Modify the code in
dfs() to return the path when a node with the target value is discovered.
Now let’s run our algorithm and print the path found. We should see a list of Nodes printed to the console. The output should contain only the nodes in the path from the root to the target node. Experiment with your code by searching for other values in the tree. What happens if you search for a value that’s not in the tree?