content: package codingquestions.leetcode;
  
  /**
   * 2458. Height of Binary Tree After Subtree Removal Queries
   * Solved
   * Hard
   * Topics
   * Companies
   * Hint
   * You are given the root of a binary tree with n nodes. Each node is assigned a unique value from 1 to n. You are also given an array queries of size m.
   * <p>
   * You have to perform m independent queries on the tree where in the ith query you do the following:
   * <p>
   * Remove the subtree rooted at the node with the value queries[i] from the tree. It is guaranteed that queries[i] will not be equal to the value of the root.
   * Return an array answer of size m where answer[i] is the height of the tree after performing the ith query.
   * <p>
   * Note:
   * <p>
   * The queries are independent, so the tree returns to its initial state after each query.
   * The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.
   **/
  
  import codingquestions.leetcode.ds.TreeNode;
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   * int val;
   * TreeNode left;
   * TreeNode right;
   * TreeNode() {}
   * TreeNode(int val) { this.val = val; }
   * TreeNode(int val, TreeNode left, TreeNode right) {
   * this.val = val;
   * this.left = left;
   * this.right = right;
   * }
   * }
   */
  public class HeightofBinaryTreeAfterSubtreeRemovalQueries {
  
      static final int[] heights = new int[100001];
      int maxHeight = 0;
  
      public int[] treeQueries(TreeNode root, int[] queries) {
          getLeftHeights(root, 0);
          maxHeight = 0;
          getRightHeights(root, 0);
  
          int n = queries.length;
          int[] result = new int[n];
          for (int i = n - 1; i >= 0; i--) {
              result[i] = heights[queries[i]];
          }
  
          return result;
      }
  
      private void getLeftHeights(TreeNode node, int height) {
          heights[node.val] = maxHeight;
          maxHeight = Math.max(maxHeight, height);
          if (node.left != null) getLeftHeights(node.left, height + 1);
          if (node.right != null) getLeftHeights(node.right, height + 1);
      }
  
      private void getRightHeights(TreeNode node, int height) {
          heights[node.val] = Math.max(heights[node.val], maxHeight);
          maxHeight = Math.max(height, maxHeight);
          if (node.right != null) getRightHeights(node.right, height + 1);
          if (node.left != null) getRightHeights(node.left, height + 1);
      }
  }
  