C# | Detailed Explanation + Dry Run | Level Order Traversal
Intuition\nFor this problem my first intuition was to iterate over the queries array and call a RemoveNode function for each of the query nodes. The Remove func
# Intuition\nFor this problem my first intuition was to iterate over the queries array and call a RemoveNode function for each of the query nodes. The Remove function would mark the node as null at its parent and calculate the tree\'s new height after that action. But the problem statement mentions that the state of the tree resets to the original after every query operation. That presented a problem with my initial approach. After this I decided to store multiple deep copies of the original array for every index i in queries array. I did that and ran the code. The code worked for all but last 5 test cases. I changed my approach to not modify the original array but just return the control from the calculateHeight function when finding the query node, but that too required a full travsersal every time a query node is called and hence a time complexity of O(m*n) where m is the query array length and n is the tree node count. \nI was stuck at this stage for quite some time and decided to see the existing submitted solutions. I found Bakerston\'s submission here \nhttps://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/solutions/2757990/python-3-explanation-with-pictures-dfs/\n\nI am using his logic but tried to code it in a slighly different way using Level Order Traversal. \n \n\n# Approach\n\nUsed the below example for dry run :- \n\nroot =\n[5,8,9,2,1,3,7,4,6]\n\nqueries =\n[3,4,2,8]\n\n![image.png](https://assets.leetcode.com/users/images/187736d3-99e1-488c-80bb-52f9bd154b45_1689529471.9606593.png)\n\n\nThe approach I took here makes use of precomputed values which would help us reduce the time complexity from O(m*n) where m = length of queries, n = nodes in tree using the stabdard DFS approach to a time complexity of O(N) where N = node count in the original tree.\n\nFirst we populate the structure \'nodeHeightsMap\'. It stores the map of tree node to its corresponding height. It makes use of the standard Height finding algorithm. \n\nSecond we call the standard \'Level Order Traversal\' also known as the Breadth First Search in case of Graphs. Here by making use of the Queue structure we store all the nodes at a particular level in a map structure called \'LevelByChildren\', where key is the current level and value is the list of all nodes at that particular level.\nWhile iterating doing this traversal we also store a mapping of node to level so that we know that what level does a particular node belong to, so that we can later do a look up on that.\n\n![image.png](https://assets.leetcode.com/users/images/ebd2b2b2-458f-46f9-889e-7679351cf9ab_1689529514.1232116.png)\n\n\nThirdly we will need sort each list in the \'LevelByChildrenMap\' structure by height since we need just 2 largest values for our calculation. You will understand this by going over the point b) in the below passage. \n\n![image.png](https://assets.leetcode.com/users/images/2c86e8e4-fae9-4575-ae8e-3a44384ab40f_1689529611.9011755.png)\n\n\nOnce we have all these precomputed values stored it is time for the logic of the problem. \na) We find all the cousins for that query node. What that means is we pull all the nodes which are at the same level as this node from the map structure \'LevelByChildrenMap\'.\nb) What we are trying to do is if there are more that one cousins at the same level we will use its height to calculate the height of the tree. We do this by adding the node\'s height + node\'s depth that would effectively give us the totol tree height.\nc) In case there is only one node at that level which is the query node, and since we need to remove this, we return \'level-1\' level essentially here is the depth of the node. \nd) One thing to remember here is at every level we just need to maintain just two nodes with max height since both will never be deleted together.\n\n**Dry Run** **:-**\n\n![image.png](https://assets.leetcode.com/users/images/e1d99f8e-d4c2-42ab-99c8-f57e9d6e5fdb_1689529649.4426959.png)\n\n\n# Complexity\n- Time complexity: O(N) N is the node count \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N) N is the node count\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# **If you found my solution and explanation helpful, please consider upvoting it. Your upvote will help rank it higher among other solutions, making it easier for people seeking assistance to find. Feel free to ask any follow-up questions in the comment section. Thank you for reading!**\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\npublic class Solution {\n    public int[] TreeQueries(TreeNode root, int[] queries) \n    {\n        int[] result = new int[queries.Length];\n       \n        Dictionary<int,int> nodeHeightsMap = new();\n        Dictionary<int,int> nodeLevelMap  = new();\n        Dictionary<int,List<int>> LevelByChildrenMap = new();\n\n        CalculateHeightsOfAllNodes(root,nodeHeightsMap);\n\n        LevelOrderTravsersal(root,LevelByChildrenMap,nodeLevelMap);\n\n        foreach(KeyValuePair<int,List<int>> entry in LevelByChildrenMap)\n        {\n             entry.Value.Sort((a, b) =>\n                 {\n                        if (nodeHeightsMap[a] > nodeHeightsMap[b])\n                        {\n                            return -1;\n                        }\n                        else if (nodeHeightsMap[a] < nodeHeightsMap[b])\n                        {\n                            return 1;\n                        }\n                        else\n                        {\n                            return 0;\n                        }\n                 });\n        }\n\n        for(int i = 0 ; i < queries.Length ; i++)\n        {\n            int level = nodeLevelMap[queries[i]];\n            List<int> ChildrenAtLevel = LevelByChildrenMap[level];\n\n            if(ChildrenAtLevel.Count == 1)\n            {\n               result[i] = level-1;\n            }\n            else\n            {\n               foreach(int child in ChildrenAtLevel)\n               {\n                   if(child != queries[i])\n                   {\n                       result[i] = nodeLevelMap[child]+nodeHeightsMap[child];\n                       break; \n                   }\n               }\n            }\n        }\n\n        return result;\n    }\n    public int CalculateHeightsOfAllNodes(TreeNode root,Dictionary<int,int> heights)\n    {\n        if(root == null) return -1;\n\n        int height = Math.Max(CalculateHeightsOfAllNodes(root.left,heights),CalculateHeightsOfAllNodes(root.right,heights))+1;\n\n        heights.Add(root.val,height);\n\n        return height;\n    }\n    private void LevelOrderTravsersal(TreeNode root,Dictionary<int,List<int>> LevelByChildren,Dictionary<int,int> nodeLevelMap)\n    {\n        Queue<TreeNode> queue = new Queue<TreeNode>();\n        queue.Enqueue(root);\n        queue.Enqueue(null);\n        int level = 0;\n        List<int> curr = new List<int>();\n        while(queue.Count != 0)\n        {\n            TreeNode temp = queue.Dequeue();                   \n            if(temp != null)\n            {\n               curr.Add(temp.val);\n               nodeLevelMap.Add(temp.val,level);\n               if(temp.left != null) queue.Enqueue(temp.left);\n\n               if(temp.right != null) queue.Enqueue(temp.right);\n            }\n            else\n            {\n                List<int> newList = new List<int>(curr);\n                LevelByChildren.Add(level,newList);\n                level++;             \n                curr.Clear();\n                if(queue.Count != 0)\n                {\n                   queue.Enqueue(null);\n                }\n            }\n        }\n    }\n}\n```
['Tree', 'Breadth-First Search', 'C#']