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.