This is our solution and implementation to problem #2458: Height of Binary Tree After Subtree Removal Queries 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: Height of Binary Tree After Subtree Removal Queries on LeetCode.
Problem Analysis
We are given a root node of a tree root and a set of queries. The response of each query will be the height of the tree if the node with value queries[i] were not a part of the tree. We don't know the size of the tree ahead of time beacuse we initially only have access to the root node. To determine the number of nodes and other information about the tree, we would need to traverse it.
Each query is independent of the other queries, so a "deletion" of a node in one query does not hold in the subsequent queries. Therefore, we should avoid taking an approach that actually removes nodes from the tree. Insted, we should collect information about the depth of each node and the max depth below the node, then use this information to find the response to each query without changing anything about the tree itself.
Implementation Strategy
We will initially iterate the tree to collect information:
- We will record the depth of each node in a map depths that maps node values to their depths.
- For each node, we will determine the maximum depth of any path that has that node and store in the map maxDepths that maps node values to their maximum depths.
- For each node, we will store a reference to its parent node in map parentNodes that maps the nodes value to its parent.
The method determineDepths does this recursively:
- Assign maxDepth with the value of currentDepth given as an argument.
- For the left and right nodes (if they exist):
- Add an entry to parentNodes to link the child node to startNode given as an argument.
- Recursively call determineDepths to get the max depth of that child node and assign to maxDepth if it is larger than the existing value.
- Add startNode.val -> maxDepth in maxDepths
- Add startNode.val -> currentDepth in depths
- Return maxDepth.
This will recursively determine the maximum depth of each node and store it in the structures we created initially.
Then, for each query in queries:
- Set outputVal to 0 (this will be the query response).
- Find the query node's parentNode using our map parentNodes.
- If the parentNode only has one child, set outputVal to depths.get(parentNode). We do this because the parent node will no longer have children, so its depth will be it's new max depth.
- If the parent node has two children, set outputVal to maxDepths.get(childNodeValue), using the child that isn't the node to be deleted.
- Iteratively move up the path to see if this deletion affects anything:
- Assign parentNode to its own parent.
- Check if the parent node's other child has a greater max depth. If it does, then this deletion doesn't affect the max depth of the tree, so return that immediately.
- If not, repeat this loop.
This traverses the path up, updating the outputVal with the max value found so far, and either returns that or an original max depth if nothing is affected.
Space and Time Complexity
The time complexity of determining the depth values is O(n) where n is the number of nodes in the tree. To determine the depth values, this algorithm visits each node exactly once. Then, to determine the subtree removal, the time complexity is also O(n) as, in the worst case scenario, every node needs to be visited. In this operation, some or all nodes between the node to delete and root need to be traversed, and in the worst case scenario, all nodes will be in that path. In most cases, only a fraction of the nodes will be in that path
The space complexity is O(n) as we are storing information for each node.
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.