Simple DFS
Intuition\nDepth of a node-> maximum number of edges from the node to any leaf node.\nlevel of a node-> number of edges from root node to the node.\nFind the de
# Intuition\nDepth of a node-> maximum number of edges from the node to any leaf node.\nlevel of a node-> number of edges from root node to the node.\nFind the depth and level of each node. For each level, We just need two nodes in the level with 1st maximum of level+depth and 2nd maximum of level+depth of those nodes in that level.\nFor each query, if current node is the node that contains maximum of level+depth, then return 2nd maximum. If there is only one node in that level, then return level-1;\n\n# Approach\nAs we know max node value is 100000.\nStep -1: Take two arrays level[], depth[] of max size and consider those indices as node.val.\nStep-2: Store level and depth of each node while travering the tree using DFS.\nStep-3: Take another 2d array leveldDepth[] of "maxDepth" rows, 2 columns. Consider teach row index as level. \na. First column (index 0) contains first maximum level+depth for that level.\nb. 2nd column(index 1) contains 2nd maximum level+depth.\nStep-4: Store depth of the tree in each leevl for each specific node i.e, level+depth of a node.\nStep-5: \na. Iterate over the given queries. For each query i.e, for each node val, take level and depth of the node from the level[], depth[] arrays.\nb. Comapre it with first maximum of level+depth in levelDepth array using the node level.\ncase-i (only one node in the level): the its previous level will be the answer for the query\ncase - ii (more than one node in the level): if curr node is the one that conatains the 1st maximum level+depth in that level, 2nd maximum will be answer otherwise first maximum will be answer for that query\n\n# Complexity\n- Time complexity:\nO(N) = N+100000+N = 2N+100000= 300000 (N= 100000 in worst case)= 3N\n\nN -> Number of node in the given tree.\nTraversing the tree = N nodes.\nTraversing from 1 to 100000 = 100000\nTraversing the queries = Q (N in worst case)\n- Space complexity:\nO(N)=100000+100000+ maxDepth (100000 in worst case) = 300000 (N=100000 in worst case) = 3N\n\n# Code\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 */\nclass Solution {\n    private int height(TreeNode root,int l,int[] depth,int[] level){\n        if(root==null) return 0;\n        int left=0;\n        int right=0;\n        level[root.val]=l;\n        if(root.left!=null) left=1+height(root.left,l+1,depth,level);\n        if(root.right!=null) right=1+height(root.right,l+1,depth,level);\n        return depth[root.val]= Math.max(left,right);\n    }\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        final int n=(int)(1e5)+1;\n        int[] depth=new int[n];\n        int[] level=new int[n];\n        int maxDepth=height(root,0,depth,level);\n        int[][] levelDepth=new int[maxDepth+1][2];\n        for(int i=0;i<n;i++){\n            int l=level[i];\n            int h=depth[i];\n            if(l+h>levelDepth[l][0]){\n                levelDepth[l][1]=levelDepth[l][0];\n                levelDepth[l][0]=l+h;\n            }\n            else if(l+h>levelDepth[l][1]){\n                levelDepth[l][1]=l+h;\n            }\n        }\n        int[] queryAns=new int[queries.length];\n        for(int i=0;i<queries.length;i++){\n            int nodeVal=queries[i];\n            int l=level[nodeVal];\n            if(levelDepth[l][1]==0){\n                queryAns[i]=l-1;\n            }\n            else{\n                int d=depth[nodeVal];\n                if(l+d==levelDepth[l][0]){\n                    queryAns[i]=levelDepth[l][1];\n                }\n                else{\n                    queryAns[i]=levelDepth[l][0];\n                }\n            }\n        }\n        return queryAns;\n    }\n}\n```
['Depth-First Search', 'Recursion', 'Java']