Recursion
File Destroyer
You're given a folder represented by a binary tree node root. You want to delete this folder, but before you delete a folder, you must completely empty its contents. Return the order of folders that you should delete, in order to completely delete the root folder.
You can return folders in any valid order, and folder names will be unique.
Example:
Here's one valid solution, which only deletes empty folders:
Explanation: We first delete the empty bottom folders, D, E and F. We then delete their parents B and C. We then delete their parents A. At each point, we only delete empty folders, so this is a valid solution.
0. Problem
In this problem, we want to walk through every node in the the tree and delete it. We can only delete empty folders, though. This means before we delete any node, we first have to delete all its children. We'll create a function that deletes all the nodes in a tree in the correct order.
1. Recursion
The recursion is to first delete all the children, and then only afterwards delete the current node. Here's the recursion:
This is technically a postorder traversal since it deletes the left and right children before deleting the current node, L R c.
2. Base case
The recursion will call itself on deeper and deeper nodes in the tree. Eventually, it gets called on a null node deleteAll(null), which results in an error, since the recursion uses null.left and null.right here. We have to fix this error. Instead of using the recursion, deleteAll shouldn't do anything to a null node.
3. Code
To code this up, you combine the Recursion and Base case.
Time Complexity O(n). We walk through all the nodes of the tree, which is n nodes total.
Space Complexity O(n). The recursive function calls are stored inside of the Call Stack.