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.
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
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
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
sample_root_node as the
"F" as the
target. Output the result to the terminal using