Java 2 pass DFS with HashMaps
\nclass Solution {\n    private Map<Integer, Integer> leftMap = new HashMap<>();\n    private Map<Integer, Integer> rightMap = new HashMap<>();\n    private Map
```\nclass Solution {\n    private Map<Integer, Integer> leftMap = new HashMap<>();\n    private Map<Integer, Integer> rightMap = new HashMap<>();\n    private Map<Integer, Integer> removed = new HashMap<>();\n    \n    public int[] treeQueries(TreeNode root, int[] queries) {\n        populateHeights(root, 0);\n        calculateRemovedHeights(root, 0);\n        \n        int[] output = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            output[i] = removed.get(queries[i]);\n        }\n        return output;\n    }\n    \n\t// height is the max tree height with this node removed\n    private void calculateRemovedHeights(TreeNode node, int height) {\n        if (node == null) {\n            return;\n        }\n        removed.put(node.val, height);\n\t\t\n\t\t// for each child, the height when removed is the max of the the height following\n\t\t// the opposite child, or the passed-in height with this node removed\n        calculateRemovedHeights(node.left, Math.max(height, rightMap.get(node.val)));\n        calculateRemovedHeights(node.right, Math.max(height, leftMap.get(node.val)));\n    }\n    \n\t// populate the maps with the total height of the left and right subtree of\n\t// each node, and return the larger of the two values\n    private int populateHeights(TreeNode node, int height) {\n        if (node == null) {\n            return height - 1;\n        }\n        \n        leftMap.put(node.val, populateHeights(node.left, height + 1));\n        rightMap.put(node.val, populateHeights(node.right, height + 1));\n        \n        return Math.max(leftMap.get(node.val), rightMap.get(node.val));\n    }\n}\n```
['Depth-First Search', 'Java']