This is our solution and implementation to problem #1110: Delete Nodes And Return Forest on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Delete Nodes And Return Forest on LeetCode.
Problem Analysis
We're given the root node of a single binary tree called root and a list of values called to_delete. For each value in that list, we need to delete the node corresponding to that value. Once we delete nodes, we'll have multiple binary trees, and we need to return the root node of each of those trees.
Let's consider just the count for a moment: how many trees would exist given the requested deletions? If a leaf node is deleted, no new trees would be created. If any other node is deleted, we would create one tree per child of that deleted node. Therefore, we can find the number of trees by counting the number of children of each deleted node.
Expanding upon this, we can solve our problem by doing a depth-first traversal over the tree. For each node, if its value is in to_delete, we can add its children to our list of new root nodes, then update its parent node to remove it as a reference.
Implementation Strategy
We will first make a set deletionSet based on the values of to_delete. This will speed up performance by letting us directly check if a value should be deleted instead of having to traverse an array each time. We'll create a list rootNodes to keep track of all new roots. If root doesn't have a value in deletionSet, we'll add it to rootNodes.
Then, we'll recursively traverse each child node in a method processNodes. This will return true if the node has been deleted and false otherwise. For each node:
- For its left and right children, call processNode. For each child, iff it returns true, update node.left and/or node.right respectively.
- If this node's value is in deletionSet, add each of its children to rootNodes and return true.
- If not, return false.
Space and Time Complexity
There are two inputs, root and to_delete. We'll consider n to be the number of nodes that exist in the tree represented by root. The size of to_delete is bound by n, so we'll do our analysis in terms of n.
The time complexity is O(n), as we visit each node exactly once. Since we're using a set for to_delete, each access is in O(1) time (if we didn't use a set, this would be *O(n^2)). The space complexity is O(n), as we use a set to represent to_delete and our list of root nodes can approach n elements.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.