Recursion

Package Fever

You're a software developer, and you need to install packages in the correct order.

Given the root node of the dependency tree, where each parent package must be installed before its children packages, return a valid order in which you can install the packages.

Example:

Here's a correct solution:

\notag \texttt{=> returns ["python", "array", "hash", "set"]}

Here's an incorrect solution:

\notag \texttt{=> returns ["set", "python", "array", "hash"]}

This solution fails because the "set" package must be installed after the "python" and "hash" packages.

First Few Test Cases:

1. Recursion

In order to solve this problem, we must install the parent packages before the children packages. The recursion is to first install the package on the current node, and then afterwards install it on all the children nodes. Here's the recursion:

Another way to come up with this recursion is to think about tree traversals, since we want to walk through all the nodes in the tree. There are 3 options - preorder c L R, inorder L c R and postorder L R c.

Preorder traversals visit the current node, then all the left children, and then all the right children, c L R. This holds for every node that a preorder traversal visits. So we can use a preorder traversal here to always install the parents first, then the children. And you can confirm that the above recursion is really just a preorder traversal.

2. Base case

As usual, the traversal should stop when we get to a node that's null. Here's the base case:

3. Code

To code this up, just combine the recursion and base case.

Time Complexity $O(n)$ to loop through every node.

Space Complexity $O(n)$ for the Call Stack.