Height of tree after queries

XXX. Tree Queries

Tree

Recursion

Dynamic Programming

Problem Statement:

Given the root of a binary tree and an array of queries, determine the height of the tree after removing the node specified in each query. For each query, the height of the tree is defined as the maximum depth of its remaining nodes.

Algorithm:

The solution involves preprocessing the tree to calculate the height of subtrees and using a recursive approach to compute the height of the tree with nodes removed:

1. Populate maps to store the height of the left and right subtrees for each node.
2. Use these maps to compute the height of the tree with a specific node removed. This is done by taking the maximum height from the opposite subtree or the parent height.
3. Use the preprocessed data to efficiently answer queries about tree height after removing specific nodes.

Complexity:

Time Complexity: O(n + q), where n is the number of nodes in the tree and q is the number of queries. Preprocessing takes O(n), and each query is answered in O(1).
Space Complexity: O(n), for the maps storing subtree heights and removed heights.

Java Implementation:

public class Solution {
    private Map leftMap = new HashMap<>();
    private Map rightMap = new HashMap<>();
    private Map removed = new HashMap<>();

    public int[] treeQueries(TreeNode root, int[] queries) {
        populateHeights(root, 0);
        calculateRemovedHeights(root, 0);

        int[] output = new int[queries.length];
        for (int i = 0; i < queries.length; i++) 
            output[i] = removed.get(queries[i]);

        return output;
    }

    // Calculate the height of the tree when a specific node is removed
    private void calculateRemovedHeights(TreeNode node, int height) {
        if (node == null) {
            return;
        }
        removed.put(node.val, height);

        // For each child, calculate height using opposite subtree or parent height
        calculateRemovedHeights(node.left, Math.max(height, rightMap.get(node.val)));
        calculateRemovedHeights(node.right, Math.max(height, leftMap.get(node.val)));
    }

    // Populate subtree heights for left and right children of each node
    private int populateHeights(TreeNode node, int height) {
        if (node == null) 
            return height - 1;

        leftMap.put(node.val, populateHeights(node.left, height + 1));
        rightMap.put(node.val, populateHeights(node.right, height + 1));

        return Math.max(leftMap.get(node.val), rightMap.get(node.val));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}