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.
Run the code to see the tree we’ll be using to test our implementation.