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.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?