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