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.

### Instructions

**1.**

Run the code to see the tree we’ll be using to test our implementation.