Learn about depth-first tree traversal in Python.

Depth-First Search: Python

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.

The Finishing Touches

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`.


Finding a Path

To begin, let's define our depth-first search function signature. We’ll start by writing a simple function to check if a provided tree node matches a given target value. If we have a match, then we return the node.

Getting Started

Let's implement the recursive version of the depth-first search algorithm in Python. We'll use our `TreeNode` class to store the collection of values to search through. We'll begin by implementing the basic recursive algorithm to search for a node with a specified value. Then we'll extend the recursive function to also find the path from the root node to the target node. 

Recall that our `TreeNode` implementation only stores references from parents to their children, so we'll need to keep track of the path as we search. If the `TreeNode` class also had references from child to parent, then given a `node` that isn't a root node, we could simply follow the path up to the root by calling `node.parent` in a loop until we reach the root node.

Introduction

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.

Getting Recursive

Congratulations on implementing the depth-first search algorithm in Python!

To recap this lesson, you gained practice with:
- Using the `TreeNode` class to store a tree data structure.
- Implementing a recursive method that searches for a path to a node with a specified value using the recursive paradigm often called “divide and conquer.”
- Default function arguments in Python.
- Tuples, which are immutable lists, can be a convenient choice over lists for recursive methods like this.
- Python will implicitly return `None` from functions that terminate without reaching a `return` statement, but it can be a good practice to explicitly return `None` when other components expect `None` to be returned sometimes.
