Simple Intiutive Solution | 2 Passes | 97.11% beats | Beginner Friendly
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, we need to understand how removing a node affects the height of 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, we need to understand how removing a node affects the height of a binary tree. The main idea is to find out the maximum height of the remaining tree when a node is removed. For each node in the tree, if we remove it, the new tree\'s height can be determined based on the heights of its sibling nodes and parent nodes.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Calculate Heights: Use DFS to find the height of each subtree.\n2. BFS Traversal: Perform a level-order traversal, tracking the maximum and second maximum heights at each level.\n3. Update Heights: Update each node\'s height based on whether it is the maximum or not at its level.\n4. Answer Queries: Return the precomputed heights for each queried node.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n![image.png](https://assets.leetcode.com/users/images/1a14ea69-281f-4474-b7ba-a11a21e9ba35_1729932257.5170844.png)\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\n    //height array\n    int height[100001];\n    // function to calculate heights of all substrees \n    int calHeight(TreeNode* root){\n        if(root==NULL)return 0;\n        int lef=calHeight(root->left);\n        int rig=calHeight(root->right);\n        height[root->val]=max(lef,rig);\n        return max(lef,rig)+1;\n    }\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        // array for storing height of tree if that index node is deleted \n        int newheight[100001];\n        calHeight(root);\n        // BFS queue\n        queue<TreeNode*>q;\n        q.push(root);\n        // count of level\n        int lev=0;\n        while(!q.empty()){\n            int n=q.size();\n            // if only one node\n            if(n==1){\n                TreeNode* curr=q.front();\n                q.pop();\n                // store the level of upper tree as removing this node we\'ll not include this level so that\'s why level-1\n                newheight[curr->val]=lev-1;\n                lev++;\n                if(curr->left)q.push(curr->left);\n                if(curr->right)q.push(curr->right);\n                continue;\n            }\n            // calculate the nodes havng max and second max value\n            int maxi=0,secmaxi=0;\n            for(int i=0;i<n;i++){\n                TreeNode* curr=q.front();\n                if(height[curr->val]>height[maxi]){\n                    secmaxi=maxi;\n                    maxi=curr->val;\n                }\n                else if(height[curr->val]>height[secmaxi]){\n                    secmaxi=curr->val;\n                }\n                q.pop();\n                q.push(curr);\n            }\n            while(n--){\n                TreeNode* curr=q.front();\n                q.pop();\n                // node is max and then add level of 2nd max\n                if(curr->val==maxi){\n                    newheight[curr->val]=lev+height[secmaxi];\n                }\n                else newheight[curr->val]=lev+height[maxi];\n                if(curr->left)q.push(curr->left);\n                if(curr->right)q.push(curr->right);\n            }\n            lev++;\n        }\n        // store the ans\n        for(int &i:queries){\n            i=newheight[i];\n        }\n        return queries;\n    }\n};\n```\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nimport java.util.*;\n\nclass Solution {\n    //height array\n    private int[] height = new int[100001];\n\n    // Function to calculate the height of each subtree\n    private int calHeight(TreeNode root) {\n        if (root == null) return 0;\n        int leftHeight = calHeight(root.left);\n        int rightHeight = calHeight(root.right);\n        height[root.val] = Math.max(leftHeight, rightHeight);\n        return Math.max(leftHeight, rightHeight) + 1;\n    }\n\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        // array for storing height of tree if that index node is deleted \n        int[] newHeight = new int[100001];\n        calHeight(root); // Calculate initial heights\n\n        Queue<TreeNode> q = new LinkedList<>();\n        q.offer(root);\n        int level = 0;\n\n        while (!q.isEmpty()) {\n            int n = q.size();\n            // if only one node\n            if (n == 1) {\n                TreeNode curr = q.poll();\n                newHeight[curr.val] = level - 1;\n                level++;\n                if (curr.left != null) q.offer(curr.left);\n                if (curr.right != null) q.offer(curr.right);\n                continue;\n            }\n        \n            int maxIdx = 0, secondMaxIdx = 0;\n            // Find maximum and second maximum heights\n            for (int i = 0; i < n; i++) {\n                TreeNode curr = q.poll();\n                if (height[curr.val] > height[maxIdx]) {\n                    secondMaxIdx = maxIdx;\n                    maxIdx = curr.val;\n                } else if (height[curr.val] > height[secondMaxIdx]) {\n                    secondMaxIdx = curr.val;\n                }\n                q.offer(curr);\n            }\n\n            // Update newHeight for each node in the current level\n            for (int i = 0; i < n; i++) {\n                TreeNode curr = q.poll();\n                if (curr.val == maxIdx) {\n                    newHeight[curr.val] = level + height[secondMaxIdx];\n                } else {\n                    newHeight[curr.val] = level + height[maxIdx];\n                }\n                if (curr.left != null) q.offer(curr.left);\n                if (curr.right != null) q.offer(curr.right);\n            }\n            level++;\n        }\n\n        // Process the queries\n        for (int i = 0; i < queries.length; i++) {\n            queries[i] = newHeight[queries[i]];\n        }\n\n        return queries;\n    }\n}\n\n```
['Array', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++', 'Java']