Simple DFS Solution using TreeMap JAVA Code with Video Explanation in Hindi
Time Complexity :- O(n.log(n));\n\nExplanation :- https://www.youtube.com/watch?v=doCIdDHxgbw\n\nJAVA Code :-\n\n\n/**\n * Definition for a binary tree node.\n 
**Time Complexity :- O(n.log(n));**\n\n**Explanation :-** https://www.youtube.com/watch?v=doCIdDHxgbw\n\n**JAVA Code :-**\n\n```\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 */\nclass Solution {\n    // Time Complexity :- O(n.log(n));\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        int m = maximum_value(root);\n        int[] depth = new int[m+1];\n        int[] level = new int[m+1];\n        \n        dfs(root,0,depth,level);\n        \n        // level -> (depth -> frequency)\n        TreeMap<Integer,TreeMap<Integer,Integer>> map = new TreeMap<>();\n        for(int i=1;i<=m;i++) {\n            int l = level[i];\n            int v = i;\n            TreeMap<Integer,Integer> m1;\n            if(map.containsKey(l)) {\n                m1 = map.get(l);\n                if(m1.containsKey(depth[v])) {\n                    m1.put(depth[v],m1.get(depth[v])+1);\n                } else {\n                    m1.put(depth[v],1);\n                }\n            } else {\n                m1 = new TreeMap<>();\n                m1.put(depth[v],1);\n            }\n            map.put(l,m1);\n        }\n        \n        \n        // System.out.println(map);\n        for(int i=0;i<queries.length;i++) {\n            int q = queries[i];\n            int ans = level[q]-1;\n            TreeMap<Integer,Integer> m1 = map.get(level[q]);\n            \n            if(m1.get(depth[q])==1) {\n                m1.remove(depth[q]);\n            } else {\n                m1.put(depth[q],m1.get(depth[q])-1);\n            }\n            \n            if(m1.size()>0) {\n                ans+=m1.lastKey();\n            }\n            \n            if(m1.containsKey(depth[q])) {\n                m1.put(depth[q],m1.get(depth[q])+1);\n            } else {\n                m1.put(depth[q],1);\n            }\n            \n            queries[i]=ans;\n        }\n        return queries;\n        \n    }\n    \n    public static int maximum_value(TreeNode root) {\n        if(root==null) return 0;\n        int a1 = maximum_value(root.left);\n        int a2 = maximum_value(root.right);\n        \n        return Math.max(a1,Math.max(a2,root.val));\n    }\n    \n    \n    public static int dfs(TreeNode root,int lvl,int[] depth,int[] level) {\n        if(root==null) {\n            return 0;\n        }\n        \n        \n        level[root.val]=lvl;\n        \n        int a1 =dfs(root.left,lvl+1,depth,level);\n        int a2 =dfs(root.right,lvl+1,depth,level);\n        \n        return depth[root.val]=Math.max(a1,a2)+1;\n    }\n}\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Java']