LeetCode 2458: Height of Binary Tree After Subtree Removal Queries Solution

Master LeetCode problem 2458 (Height of Binary Tree After Subtree Removal Queries), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2458. Height of Binary Tree After Subtree Removal Queries

Hard

Array Tree Depth-First Search Breadth-First Search Binary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform depth-first search (DFS) to traverse the tree and remove the subtree rooted at a specific node as requested in each query. We can maintain the heights of the tree after each query and return them in the final answer array.

We first create a map to store the parent-child relationships for each node in the tree.
We then perform a DFS traversal to build the parent-child relationships and calculate the height of each node.
For each query, we remove the subtree rooted at the queried node and update the heights of the affected nodes.
We return the heights of the tree after each query.

Time Complexity: O(n + m) where n is the number of nodes in the tree and m is the number of queries. Space Complexity: O(n) for maintaining the parent-child relationships and heights.

Solution Code

class Solution {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] heights;
    
    public int[] heightHelper(TreeNode node) {
        if (node == null) return new int[0];
        
        int left = 0, right = 0;
        if (node.left != null) {
            int[] l = heightHelper(node.left);
            left = 1 + Math.max(l[0], l[1]);
        }
        if (node.right != null) {
            int[] r = heightHelper(node.right);
            right = 1 + Math.max(r[0], r[1]);
        }
        
        heights[node.val] = Math.max(left, right);
        return new int[]{left, right};
    }
    
    public int[] removeSubtreesAndReturnHeights(TreeNode node, int[] queries) {
        for (int q : queries) graph.put(q, new ArrayList<>());
        
        heightHelper(node);
        
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            for (int child : graph.get(query)) {
                heights[child] = 0;
            }
            result[i] = heights[node.val];
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2458 (Height of Binary Tree After Subtree Removal Queries)?

This page provides optimized solutions for LeetCode problem 2458 (Height of Binary Tree After Subtree Removal Queries) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2458 (Height of Binary Tree After Subtree Removal Queries)?

The time complexity for LeetCode 2458 (Height of Binary Tree After Subtree Removal Queries) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2458 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2458 in Java, C++, or Python.

Back to LeetCode Solutions