Great! Now we have a simple function that checks if a given node has the same value as the target parameter provided. If they match, the node is returned, if not, None is returned. But we want to do more than check the root node. If the root node’s value does not match our target, then we need to search deeper into the tree for a match. We can accomplish this by recursively calling our function on the children of the provided root node.
Instructions
In the dfs() function, add a for loop that iterates over all children of the root and recursively calls the same function. This for loop should come after the if block and before the return None statement. Inside the for loop, store the output of the recursive calls to a variable called node_found.
When one of our recursive calls returns a value that is not None, we know we’ve found a match and can halt our search, returning the node we found.
After the recursive call, add an if statement that returns node_found if it is not equal to None.
Excellent! At this point, you should now have the basic recursive implementation of the depth-first search. Let’s test this by adding code to call the dfs() function and print the output.
Add a line or two at the end of dfs.py to call dfs() with sample_root_node as the root and "F" as the target. Output the result to the terminal using print().