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()
.