✅ Explained step by step | Beats 100% | ✅ Working 26.10.2024
python3 []\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        # Initialize arrays to store heights
```python3 []\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        # Initialize arrays to store heights and node information\n        heights = [0] * 50000  # Heights of leaf nodes\n        d = [0] * 100001      # Depth of each node\n        l = [0] * 100001      # Left index for each node\n        r = [0] * 100001      # Right index for each node\n        len_leaves = 0        # Counter for leaf nodes\n        \n        def search(p: TreeNode, h: int) -> None:\n            nonlocal len_leaves\n            d[p.val] = h  # Store current node\'s depth\n            \n            # If leaf node found\n            if not p.left and not p.right:\n                heights[len_leaves] = h    # Store leaf height\n                l[p.val] = r[p.val] = len_leaves  # Both indices same for leaf\n                len_leaves += 1\n                return\n            \n            l[p.val] = len_leaves  # Store left index for current node\n            \n            # Recursively process left and right subtrees\n            if p.left:\n                search(p.left, h + 1)\n            if p.right:\n                search(p.right, h + 1)\n                \n            r[p.val] = len_leaves - 1  # Store right index for current node\n        \n        # Process the tree starting from root\n        search(root, 0)\n        \n        n = len_leaves  # Total number of leaf nodes\n        maxl = [0] * n  # Max heights from left\n        maxr = [0] * n  # Max heights from right\n        \n        # Build prefix and suffix maximum arrays\n        for i in range(1, n):\n            maxl[i] = max(maxl[i-1], heights[i-1])  # Max height from left\n            maxr[n-i-1] = max(maxr[n-i], heights[n-i])  # Max height from right\n        \n        ret = []  # Result list\n        \n        # Process each query\n        for query in queries:\n            # Find maximum height excluding current node\'s subtree\n            maxxl = maxl[l[query]]  # Max height to the left\n            maxxr = maxr[r[query]]  # Max height to the right\n            # Result is max of (max left height, max right height, current depth-1)\n            ret.append(max(max(maxxl, maxxr), d[query]-1))\n        \n        return ret\n```\n```cpp []\nclass Solution {\npublic:\n    // Array to store the maximum height of the tree after removing each node\n    int maxHeightAfterRemoval[100001];\n    int currentMaxHeight = 0;\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        traverseLeftToRight(root, 0);\n        currentMaxHeight = 0;  // Reset for the second traversal\n        traverseRightToLeft(root, 0);\n\n        // Process queries and build the result vector\n        int queryCount = queries.size();\n        vector<int> queryResults(queryCount);\n        for (int i = 0; i < queryCount; i++) {\n            queryResults[i] = maxHeightAfterRemoval[queries[i]];\n        }\n\n        return queryResults;\n    }\n\nprivate:\n    // Left to right traversal\n    void traverseLeftToRight(TreeNode* node, int currentHeight) {\n        if (node == nullptr) return;\n\n        // Store the maximum height if this node were removed\n        maxHeightAfterRemoval[node->val] = currentMaxHeight;\n\n        // Update the current maximum height\n        currentMaxHeight = max(currentMaxHeight, currentHeight);\n\n        // Traverse left subtree first, then right\n        traverseLeftToRight(node->left, currentHeight + 1);\n        traverseLeftToRight(node->right, currentHeight + 1);\n    }\n\n    // Right to left traversal\n    void traverseRightToLeft(TreeNode* node, int currentHeight) {\n        if (node == nullptr) return;\n\n        // Update the maximum height if this node were removed\n        maxHeightAfterRemoval[node->val] =\n            max(maxHeightAfterRemoval[node->val], currentMaxHeight);\n\n        // Update the current maximum height\n        currentMaxHeight = max(currentHeight, currentMaxHeight);\n\n        // Traverse right subtree first, then left\n        traverseRightToLeft(node->right, currentHeight + 1);\n        traverseRightToLeft(node->left, currentHeight + 1);\n    }\n};\n```\n```java []\nclass Solution {\n    // Arrays to store information about the tree\n    private int[] heights;  // Stores heights of leaf nodes in order of traversal\n    private int[] d;        // Stores depth/height of each node by its value\n    private int[] l;        // Stores left boundary index for each node value\n    private int[] r;        // Stores right boundary index for each node value\n    private int lenLeaves;  // Counts number of leaf nodes encountered\n    \n    public int[] treeQueries(TreeNode root, int[] queries) {\n        // Initialize arrays with sufficient size\n        heights = new int[50000];    // For storing leaf heights\n        d = new int[100001];         // For storing node depths\n        l = new int[100001];         // For storing left boundaries\n        r = new int[100001];         // For storing right boundaries\n        lenLeaves = 0;               // Initialize leaf counter\n        \n        // DFS to process the tree and fill arrays\n        search(root, 0);\n        \n        int n = lenLeaves;\n        // Arrays to store maximum heights from left and right\n        int[] maxl = new int[n];     // Prefix maximums\n        int[] maxr = new int[n];     // Suffix maximums\n        \n        // Build prefix maximum array (left to right)\n        // At each position i, stores max height of all leaves to the left\n        for (int i = 1; i < n; i++) {\n            maxl[i] = Math.max(maxl[i-1], heights[i-1]);\n        }\n        \n        // Build suffix maximum array (right to left)\n        // At each position i, stores max height of all leaves to the right\n        for (int i = n-2; i >= 0; i--) {\n            maxr[i] = Math.max(maxr[i+1], heights[i+1]);\n        }\n        \n        // Process each query\n        int[] ret = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            int query = queries[i];\n            // Find maximum height outside the range of current node\n            int maxxl = maxl[l[query]];          // Max height to the left\n            int maxxr = maxr[r[query]];          // Max height to the right\n            // Result is maximum of left max, right max, and parent height\n            ret[i] = Math.max(Math.max(maxxl, maxxr), d[query]-1);\n        }\n        \n        return ret;\n    }\n    \n    // DFS to process the tree\n    private void search(TreeNode p, int h) {\n        d[p.val] = h;    // Store current node\'s height\n        \n        // If current node is a leaf\n        if (p.left == null && p.right == null) {\n            heights[lenLeaves] = h;   // Store leaf height\n            l[p.val] = r[p.val] = lenLeaves;  // Both boundaries point to same index\n            lenLeaves++;              // Increment leaf counter\n            return;\n        }\n        \n        l[p.val] = lenLeaves;        // Store left boundary\n        \n        // Recursively process left and right subtrees\n        if (p.left != null) {\n            search(p.left, h + 1);\n        }\n        if (p.right != null) {\n            search(p.right, h + 1);\n        }\n        \n        r[p.val] = lenLeaves - 1;    // Store right boundary\n    }\n}\n```\n```csharp []\npublic class Solution {\n    // Array to store heights of leaf nodes\n    private int[] heights;\n    \n    // Array to store depth of each node\n    private int[] d;\n    \n    // Arrays to store left and right boundaries of subtrees in the leaf array\n    private int[] l;\n    private int[] r;\n    \n    // Counter for number of leaf nodes\n    private int lenLeaves;\n    \n    public int[] TreeQueries(TreeNode root, int[] queries) {\n        // Initialize arrays with sufficient size\n        // heights stores leaf node heights\n        heights = new int[50000];\n        // d stores depth of each node (indexed by node value)\n        d = new int[100001];\n        // l,r store left and right boundaries of subtrees in leaf array\n        l = new int[100001];\n        r = new int[100001];\n        lenLeaves = 0;\n        \n        // DFS to process the tree and fill arrays\n        Search(root, 0);\n        \n        int n = lenLeaves;\n        // Arrays to store maximum heights from left and right\n        int[] maxl = new int[n];\n        int[] maxr = new int[n];\n        \n        // Build prefix and suffix maximum arrays\n        // maxl[i] stores maximum height from 0 to i-1\n        // maxr[i] stores maximum height from i+1 to n-1\n        for (int i = 1; i < n; i++) {\n            maxl[i] = Math.Max(maxl[i-1], heights[i-1]);\n            maxr[n-i-1] = Math.Max(maxr[n-i], heights[n-i]);\n        }\n        \n        var ret = new List<int>();\n        \n        // Process each query\n        foreach (int query in queries) {\n            // Get maximum height to the left of current node\'s subtree\n            int maxxl = maxl[l[query]];\n            // Get maximum height to the right of current node\'s subtree\n            int maxxr = maxr[r[query]];\n            // Result is max of:\n            // 1. Maximum height to the left of subtree\n            // 2. Maximum height to the right of subtree\n            // 3. Depth of current node - 1 (parent\'s depth)\n            ret.Add(Math.Max(Math.Max(maxxl, maxxr), d[query]-1));\n        }\n        \n        return ret.ToArray();\n    }\n    \n    private void Search(TreeNode p, int h) {\n        // Store current node\'s depth\n        d[p.val] = h;\n        \n        // If leaf node, store its height and boundaries\n        if (p.left == null && p.right == null) {\n            heights[lenLeaves] = h;\n            // For leaf nodes, left and right boundaries are same\n            l[p.val] = r[p.val] = lenLeaves;\n            lenLeaves++;\n            return;\n        }\n        \n        // Store left boundary of current subtree\n        l[p.val] = lenLeaves;\n        \n        // Recursively process left and right children\n        if (p.left != null) {\n            Search(p.left, h + 1);\n        }\n        if (p.right != null) {\n            Search(p.right, h + 1);\n        }\n        \n        // Store right boundary of current subtree\n        r[p.val] = lenLeaves - 1;\n    }\n}\n```\n```golang []\ntype Solution struct {\n    maxHeightAfterRemoval [100001]int\n    currentMaxHeight      int\n}\n\nfunc treeQueries(root *TreeNode, queries []int) []int {\n    sol := &Solution{}\n    \n    // First traversal from left to right\n    sol.traverseLeftToRight(root, 0)\n    \n    // Reset current max height for second traversal\n    sol.currentMaxHeight = 0\n    sol.traverseRightToLeft(root, 0)\n    \n    // Process queries and build result\n    queryResults := make([]int, len(queries))\n    for i, query := range queries {\n        queryResults[i] = sol.maxHeightAfterRemoval[query]\n    }\n    \n    return queryResults\n}\n\nfunc (s *Solution) traverseLeftToRight(node *TreeNode, currentHeight int) {\n    if node == nil {\n        return\n    }\n    \n    // Store the maximum height if this node were removed\n    s.maxHeightAfterRemoval[node.Val] = s.currentMaxHeight\n    \n    // Update current maximum height\n    s.currentMaxHeight = max(s.currentMaxHeight, currentHeight)\n    \n    // Traverse left subtree first, then right\n    s.traverseLeftToRight(node.Left, currentHeight + 1)\n    s.traverseLeftToRight(node.Right, currentHeight + 1)\n}\n\nfunc (s *Solution) traverseRightToLeft(node *TreeNode, currentHeight int) {\n    if node == nil {\n        return\n    }\n    \n    // Update maximum height if this node were removed\n    s.maxHeightAfterRemoval[node.Val] = max(\n        s.maxHeightAfterRemoval[node.Val],\n        s.currentMaxHeight,\n    )\n    \n    // Update current maximum height\n    s.currentMaxHeight = max(currentHeight, s.currentMaxHeight)\n    \n    // Traverse right subtree first, then left\n    s.traverseRightToLeft(node.Right, currentHeight + 1)\n    s.traverseRightToLeft(node.Left, currentHeight + 1)\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```swift []\nclass Solution {\n    private var maxHeightAfterRemoval = Array(repeating: 0, count: 100001)\n    private var currentMaxHeight = 0\n    \n    func treeQueries(_ root: TreeNode?, _ queries: [Int]) -> [Int] {\n        traverseLeftToRight(root, 0)\n        currentMaxHeight = 0  // Reset for second traversal\n        traverseRightToLeft(root, 0)\n        \n        // Process queries and build result array\n        return queries.map { maxHeightAfterRemoval[$0] }\n    }\n    \n    private func traverseLeftToRight(_ node: TreeNode?, _ currentHeight: Int) {\n        guard let node = node else { return }\n        \n        // Store maximum height if this node were removed\n        maxHeightAfterRemoval[node.val] = currentMaxHeight\n        \n        // Update current maximum height\n        currentMaxHeight = max(currentMaxHeight, currentHeight)\n        \n        // Traverse left subtree first, then right\n        traverseLeftToRight(node.left, currentHeight + 1)\n        traverseLeftToRight(node.right, currentHeight + 1)\n    }\n    \n    private func traverseRightToLeft(_ node: TreeNode?, _ currentHeight: Int) {\n        guard let node = node else { return }\n        \n        // Update maximum height if this node were removed\n        maxHeightAfterRemoval[node.val] = max(\n            maxHeightAfterRemoval[node.val],\n            currentMaxHeight\n        )\n        \n        // Update current maximum height\n        currentMaxHeight = max(currentHeight, currentMaxHeight)\n        \n        // Traverse right subtree first, then left\n        traverseRightToLeft(node.right, currentHeight + 1)\n        traverseRightToLeft(node.left, currentHeight + 1)\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\n\n// Function to process tree queries that finds max height excluding certain nodes\nvar treeQueries = function(root, queries) {\n    // Array to store heights of leaf nodes\n    const heights = new Array(50000).fill(0);\n    \n    // Array to store depth of each node (indexed by node value)\n    const d = new Array(100001).fill(0);\n    \n    // Arrays to store left and right boundaries for each node\'s subtree\n    const l = new Array(100001).fill(0);\n    const r = new Array(100001).fill(0);\n    \n    // Counter for number of leaf nodes\n    let len = 0;\n    \n    // DFS function to process the tree\n    function search(p, h) {\n        // Store current node\'s depth\n        d[p.val] = h;\n        \n        // If current node is a leaf node\n        if (!p.left && !p.right) {\n            heights[len] = h;  // Store its height\n            l[p.val] = r[p.val] = len;  // Set left and right boundaries\n            len++;  // Increment leaf counter\n            return;\n        }\n        \n        // Store left boundary for current node\n        l[p.val] = len;\n        \n        // Recursively process left and right children\n        if (p.left) search(p.left, h + 1);\n        if (p.right) search(p.right, h + 1);\n        \n        // Store right boundary for current node\n        r[p.val] = len - 1;\n    }\n    \n    // Start DFS from root\n    search(root, 0);\n    \n    const n = len;\n    // Arrays to store maximum heights from left and right\n    const maxl = new Array(n).fill(0);\n    const maxr = new Array(n).fill(0);\n    \n    // Build prefix and suffix maximum arrays\n    for (let i = 1; i < n; i++) {\n        maxl[i] = Math.max(maxl[i-1], heights[i-1]);  // Left to right max\n        maxr[n-i-1] = Math.max(maxr[n-i], heights[n-i]);  // Right to left max\n    }\n    \n    // Array to store results\n    const ret = [];\n    const k = queries.length;\n    \n    // Process each query\n    for (let i = 0; i < k; i++) {\n        // Find maximum height excluding current node\'s subtree\n        const maxxl = maxl[l[queries[i]]];  // Max height to the left\n        const maxxr = maxr[r[queries[i]]];  // Max height to the right\n        // Result is max of left max, right max, and node\'s depth-1\n        ret.push(Math.max(Math.max(maxxl, maxxr), d[queries[i]] - 1));\n    }\n    \n    return ret;\n};\n```\n```typescript [TS]\n// TypeScript\n\n\n// Function that processes queries about maximum heights in a binary tree excluding specific nodes\nfunction treeQueries(root: TreeNode | null, queries: number[]): number[] {\n    // Arrays to store various tree-related information\n    const heights: number[] = new Array(50000).fill(0);  // Stores heights of leaf nodes\n    const d: number[] = new Array(100001).fill(0);       // Stores depth of each node\n    const l: number[] = new Array(100001).fill(0);       // Stores left boundary index for each node\n    const r: number[] = new Array(100001).fill(0);       // Stores right boundary index for each node\n    let len: number = 0;                                 // Counter for leaf nodes\n    \n    // DFS function to process the tree\n    function search(p: TreeNode, h: number): void {\n        // Store current node\'s depth\n        d[p.val] = h;\n        \n        // If current node is a leaf node\n        if (!p.left && !p.right) {\n            heights[len] = h;           // Store its height\n            l[p.val] = r[p.val] = len;  // Set left and right boundaries to current index\n            len++;                      // Increment leaf counter\n            return;\n        }\n        \n        // Store left boundary for current node\n        l[p.val] = len;\n        \n        // Recursively process left and right subtrees\n        if (p.left) search(p.left, h + 1);\n        if (p.right) search(p.right, h + 1);\n        \n        // Store right boundary for current node\n        r[p.val] = len - 1;\n    }\n    \n    // Handle empty tree case\n    if (!root) return [];\n    search(root, 0);\n    \n    const n: number = len;\n    // Arrays to store maximum heights from left and right\n    const maxl: number[] = new Array(n).fill(0);\n    const maxr: number[] = new Array(n).fill(0);\n    \n    // Compute maximum heights from left to right and right to left\n    for (let i = 1; i < n; i++) {\n        maxl[i] = Math.max(maxl[i-1], heights[i-1]);     // Left to right maximums\n        maxr[n-i-1] = Math.max(maxr[n-i], heights[n-i]); // Right to left maximums\n    }\n    \n    // Process queries\n    const ret: number[] = [];\n    const k: number = queries.length;\n    \n    for (let i = 0; i < k; i++) {\n        // For each query, find maximum height possible when removing the queried node\n        const maxxl: number = maxl[l[queries[i]]];        // Max height to the left\n        const maxxr: number = maxr[r[queries[i]]];        // Max height to the right\n        // Result is maximum of:\n        // 1. Maximum height to the left of node\n        // 2. Maximum height to the right of node\n        // 3. Node\'s depth minus 1 (representing parent\'s path)\n        ret.push(Math.max(Math.max(maxxl, maxxr), d[queries[i]] - 1));\n    }\n    \n    return ret;\n}\n```\n```rust []\nuse std::cell::RefCell;\nuse std::rc::Rc;\n\nimpl Solution {\n    pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {\n        // Initialize storage vectors\n        let mut heights = vec![0; 50000];  // Stores heights of leaf nodes\n        let mut len = 0;                   // Tracks number of leaf nodes\n        let mut d = vec![0; 100001];       // Stores depth of each node\n        let mut l = vec![0; 100001];       // Stores left boundary index for each node\n        let mut r = vec![0; 100001];       // Stores right boundary index for each node\n\n        // Depth-First Search implementation\n        fn search(\n            node: Option<Rc<RefCell<TreeNode>>>,\n            h: i32,                        // Current height in tree\n            heights: &mut Vec<i32>,        // Mutable reference to heights vector\n            len: &mut usize,               // Mutable reference to length counter\n            d: &mut Vec<i32>,              // Mutable reference to depths vector\n            l: &mut Vec<i32>,              // Mutable reference to left boundaries\n            r: &mut Vec<i32>,              // Mutable reference to right boundaries\n        ) {\n            if let Some(n) = node {\n                let node = n.borrow();\n                let val = node.val as usize;\n                d[val] = h;                // Record current node\'s depth\n\n                // Handle leaf node case\n                if node.left.is_none() && node.right.is_none() {\n                    heights[*len] = h;      // Store leaf height\n                    l[val] = *len as i32;   // Set left boundary\n                    r[val] = *len as i32;   // Set right boundary\n                    *len += 1;              // Increment leaf counter\n                    return;\n                }\n\n                l[val] = *len as i32;      // Set left boundary for internal node\n\n                // Recursively process left and right subtrees\n                search(node.left.clone(), h + 1, heights, len, d, l, r);\n                search(node.right.clone(), h + 1, heights, len, d, l, r);\n\n                r[val] = (*len - 1) as i32; // Set right boundary for internal node\n            }\n        }\n\n        // Process the tree starting from root\n        search(\n            root,\n            0,\n            &mut heights,\n            &mut len,\n            &mut d,\n            &mut l,\n            &mut r,\n        );\n\n        let n = len;\n        // Arrays to store maximum heights from left and right\n        let mut maxl = vec![0; n];\n        let mut maxr = vec![0; n];\n\n        // Build prefix (left) and suffix (right) maximum arrays\n        for i in 1..n {\n            maxl[i] = maxl[i - 1].max(heights[i - 1]);    // Maximum height from left\n            maxr[n - i - 1] = maxr[n - i].max(heights[n - i]); // Maximum height from right\n        }\n\n        // Process each query and build result vector\n        queries\n            .iter()\n            .map(|&q| {\n                let q = q as usize;\n                let maxxl = maxl[l[q] as usize];          // Max height to the left\n                let maxxr = maxr[r[q] as usize];          // Max height to the right\n                maxxl.max(maxxr).max(d[q] - 1)            // Take maximum of left, right, and depth-1\n            })\n            .collect()                                     // Collect results into vector\n    }\n}\n```\n```ruby []\ndef tree_queries(root, queries)\n    # Initialize arrays to store tree information\n    # @heights: stores heights of leaf nodes\n    # @len: tracks number of leaf nodes\n    # @d: stores depth of each node\n    # @l, @r: store left and right indices for each node\'s subtree range\n    @heights = Array.new(50000, 0)\n    @len = 0\n    @d = Array.new(100001, 0)\n    @l = Array.new(100001, 0)\n    @r = Array.new(100001, 0)\n    \n    # Process the tree using DFS\n    search(root, 0)\n    \n    n = @len  # Total number of leaf nodes\n    # Arrays to store maximum heights from left and right perspectives\n    maxl = Array.new(n, 0)\n    maxr = Array.new(n, 0)\n    \n    # Build prefix and suffix maximum arrays\n    (1...n).each do |i|\n        # maxl[i] stores the maximum height of leaves to the left of index i\n        maxl[i] = [maxl[i-1], @heights[i-1]].max\n        # maxr[n-i-1] stores the maximum height of leaves to the right of index n-i-1\n        maxr[n-i-1] = [maxr[n-i], @heights[n-i]].max\n    end\n    \n    # Process each query\n    ret = []\n    queries.each do |query|\n        # Find maximum height excluding current node\'s subtree\n        maxxl = maxl[@l[query]]  # Max height to the left of subtree\n        maxxr = maxr[@r[query]]  # Max height to the right of subtree\n        # Result is maximum of: left max, right max, or depth-1\n        ret.push([maxxl, maxxr, @d[query]-1].max)\n    end\n    \n    ret\nend\n\n# DFS helper method to process the tree structure\ndef search(p, h)\n    @d[p.val] = h  # Store current node\'s depth\n    \n    # If leaf node found\n    if !p.left && !p.right\n        @heights[@len] = h  # Store leaf height\n        @l[p.val] = @r[p.val] = @len  # Mark leaf node range\n        @len += 1\n        return\n    end\n    \n    @l[p.val] = @len  # Store left boundary of current subtree\n    \n    # Recursively process left and right children\n    search(p.left, h + 1) if p.left\n    search(p.right, h + 1) if p.right\n    \n    @r[p.val] = @len - 1  # Store right boundary of current subtree\nend\n```\n### Without comments\n```python3 []\nclass Solution:\n    def treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:\n        heights = [0] * 50000\n        d = [0] * 100001\n        l = [0] * 100001\n        r = [0] * 100001\n        len_leaves = 0\n        \n        def search(p: TreeNode, h: int) -> None:\n            nonlocal len_leaves\n            d[p.val] = h\n            \n            if not p.left and not p.right:\n                heights[len_leaves] = h\n                l[p.val] = r[p.val] = len_leaves\n                len_leaves += 1\n                return\n            \n            l[p.val] = len_leaves\n            \n            if p.left:\n                search(p.left, h + 1)\n            if p.right:\n                search(p.right, h + 1)\n                \n            r[p.val] = len_leaves - 1\n        \n        search(root, 0)\n        \n        n = len_leaves\n        maxl = [0] * n\n        maxr = [0] * n\n        \n        for i in range(1, n):\n            maxl[i] = max(maxl[i-1], heights[i-1])\n            maxr[n-i-1] = max(maxr[n-i], heights[n-i])\n        \n        ret = []\n        \n        for query in queries:\n            maxxl = maxl[l[query]]\n            maxxr = maxr[r[query]]\n            ret.append(max(max(maxxl, maxxr), d[query]-1))\n        \n        return ret\n```\n```cpp []\nclass Solution {\npublic:\n    int maxHeightAfterRemoval[100001];\n    int currentMaxHeight = 0;\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        traverseLeftToRight(root, 0);\n        currentMaxHeight = 0;\n        traverseRightToLeft(root, 0);\n\n        int queryCount = queries.size();\n        vector<int> queryResults(queryCount);\n        for (int i = 0; i < queryCount; i++) {\n            queryResults[i] = maxHeightAfterRemoval[queries[i]];\n        }\n\n        return queryResults;\n    }\n\nprivate:\n    void traverseLeftToRight(TreeNode* node, int currentHeight) {\n        if (node == nullptr) return;\n\n        maxHeightAfterRemoval[node->val] = currentMaxHeight;\n        currentMaxHeight = max(currentMaxHeight, currentHeight);\n\n        traverseLeftToRight(node->left, currentHeight + 1);\n        traverseLeftToRight(node->right, currentHeight + 1);\n    }\n\n    void traverseRightToLeft(TreeNode* node, int currentHeight) {\n        if (node == nullptr) return;\n\n        maxHeightAfterRemoval[node->val] = \n            max(maxHeightAfterRemoval[node->val], currentMaxHeight);\n        currentMaxHeight = max(currentHeight, currentMaxHeight);\n\n        traverseRightToLeft(node->right, currentHeight + 1);\n        traverseRightToLeft(node->left, currentHeight + 1);\n    }\n};\n```\n```java []\nclass Solution {\n    private int[] heights;\n    private int[] d;\n    private int[] l;\n    private int[] r;\n    private int lenLeaves;\n\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        heights = new int[50000];\n        d = new int[100001];\n        l = new int[100001];\n        r = new int[100001];\n        lenLeaves = 0;\n\n        search(root, 0);\n\n        int n = lenLeaves;\n        int[] maxl = new int[n];\n        int[] maxr = new int[n];\n\n        for (int i = 1; i < n; i++) {\n            maxl[i] = Math.max(maxl[i-1], heights[i-1]);\n        }\n\n        for (int i = n-2; i >= 0; i--) {\n            maxr[i] = Math.max(maxr[i+1], heights[i+1]);\n        }\n\n        int[] ret = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            int query = queries[i];\n            int maxxl = maxl[l[query]];\n            int maxxr = maxr[r[query]];\n            ret[i] = Math.max(Math.max(maxxl, maxxr), d[query]-1);\n        }\n\n        return ret;\n    }\n\n    private void search(TreeNode p, int h) {\n        d[p.val] = h;\n\n        if (p.left == null && p.right == null) {\n            heights[lenLeaves] = h;\n            l[p.val] = r[p.val] = lenLeaves;\n            lenLeaves++;\n            return;\n        }\n\n        l[p.val] = lenLeaves;\n\n        if (p.left != null) {\n            search(p.left, h + 1);\n        }\n        if (p.right != null) {\n            search(p.right, h + 1);\n        }\n\n        r[p.val] = lenLeaves - 1;\n    }\n}\n```\n```csharp []\npublic class Solution {\n    private int[] heights;\n    private int[] d;\n    private int[] l;\n    private int[] r;\n    private int lenLeaves;\n\n    public int[] TreeQueries(TreeNode root, int[] queries) {\n        heights = new int[50000];\n        d = new int[100001];\n        l = new int[100001];\n        r = new int[100001];\n        lenLeaves = 0;\n\n        Search(root, 0);\n\n        int n = lenLeaves;\n        int[] maxl = new int[n];\n        int[] maxr = new int[n];\n\n        for (int i = 1; i < n; i++) {\n            maxl[i] = Math.Max(maxl[i-1], heights[i-1]);\n            maxr[n-i-1] = Math.Max(maxr[n-i], heights[n-i]);\n        }\n\n        var ret = new List<int>();\n\n        foreach (int query in queries) {\n            int maxxl = maxl[l[query]];\n            int maxxr = maxr[r[query]];\n            ret.Add(Math.Max(Math.Max(maxxl, maxxr), d[query]-1));\n        }\n\n        return ret.ToArray();\n    }\n\n    private void Search(TreeNode p, int h) {\n        d[p.val] = h;\n\n        if (p.left == null && p.right == null) {\n            heights[lenLeaves] = h;\n            l[p.val] = r[p.val] = lenLeaves;\n            lenLeaves++;\n            return;\n        }\n\n        l[p.val] = lenLeaves;\n\n        if (p.left != null) {\n            Search(p.left, h + 1);\n        }\n        if (p.right != null) {\n            Search(p.right, h + 1);\n        }\n\n        r[p.val] = lenLeaves - 1;\n    }\n}\n```\n```golang []\ntype Solution struct {\n    maxHeightAfterRemoval [100001]int\n    currentMaxHeight      int\n}\n\nfunc treeQueries(root *TreeNode, queries []int) []int {\n    sol := &Solution{}\n\n    sol.traverseLeftToRight(root, 0)\n\n    sol.currentMaxHeight = 0\n    sol.traverseRightToLeft(root, 0)\n\n    queryResults := make([]int, len(queries))\n    for i, query := range queries {\n        queryResults[i] = sol.maxHeightAfterRemoval[query]\n    }\n\n    return queryResults\n}\n\nfunc (s *Solution) traverseLeftToRight(node *TreeNode, currentHeight int) {\n    if node == nil {\n        return\n    }\n\n    s.maxHeightAfterRemoval[node.Val] = s.currentMaxHeight\n    s.currentMaxHeight = max(s.currentMaxHeight, currentHeight)\n\n    s.traverseLeftToRight(node.Left, currentHeight + 1)\n    s.traverseLeftToRight(node.Right, currentHeight + 1)\n}\n\nfunc (s *Solution) traverseRightToLeft(node *TreeNode, currentHeight int) {\n    if node == nil {\n        return\n    }\n\n    s.maxHeightAfterRemoval[node.Val] = max(\n        s.maxHeightAfterRemoval[node.Val],\n        s.currentMaxHeight,\n    )\n\n    s.currentMaxHeight = max(currentHeight, s.currentMaxHeight)\n\n    s.traverseRightToLeft(node.Right, currentHeight + 1)\n    s.traverseRightToLeft(node.Left, currentHeight + 1)\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```\n```swift []\nclass Solution {\n    private var maxHeightAfterRemoval = Array(repeating: 0, count: 100001)\n    private var currentMaxHeight = 0\n    \n    func treeQueries(_ root: TreeNode?, _ queries: [Int]) -> [Int] {\n        traverseLeftToRight(root, 0)\n        currentMaxHeight = 0\n        traverseRightToLeft(root, 0)\n        \n        return queries.map { maxHeightAfterRemoval[$0] }\n    }\n    \n    private func traverseLeftToRight(_ node: TreeNode?, _ currentHeight: Int) {\n        guard let node = node else { return }\n        \n        maxHeightAfterRemoval[node.val] = currentMaxHeight\n        currentMaxHeight = max(currentMaxHeight, currentHeight)\n        \n        traverseLeftToRight(node.left, currentHeight + 1)\n        traverseLeftToRight(node.right, currentHeight + 1)\n    }\n    \n    private func traverseRightToLeft(_ node: TreeNode?, _ currentHeight: Int) {\n        guard let node = node else { return }\n        \n        maxHeightAfterRemoval[node.val] = max(\n            maxHeightAfterRemoval[node.val],\n            currentMaxHeight\n        )\n        \n        currentMaxHeight = max(currentHeight, currentMaxHeight)\n        \n        traverseRightToLeft(node.right, currentHeight + 1)\n        traverseRightToLeft(node.left, currentHeight + 1)\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\n\nvar treeQueries = function(root, queries) {\n    const heights = new Array(50000).fill(0);\n    const d = new Array(100001).fill(0);\n    const l = new Array(100001).fill(0);\n    const r = new Array(100001).fill(0);\n    let len = 0;\n\n    function search(p, h) {\n        d[p.val] = h;\n\n        if (!p.left && !p.right) {\n            heights[len] = h;\n            l[p.val] = r[p.val] = len;\n            len++;\n            return;\n        }\n\n        l[p.val] = len;\n\n        if (p.left) search(p.left, h + 1);\n        if (p.right) search(p.right, h + 1);\n\n        r[p.val] = len - 1;\n    }\n\n    search(root, 0);\n\n    const n = len;\n    const maxl = new Array(n).fill(0);\n    const maxr = new Array(n).fill(0);\n\n    for (let i = 1; i < n; i++) {\n        maxl[i] = Math.max(maxl[i-1], heights[i-1]);\n        maxr[n-i-1] = Math.max(maxr[n-i], heights[n-i]);\n    }\n\n    const ret = [];\n    const k = queries.length;\n\n    for (let i = 0; i < k; i++) {\n        const maxxl = maxl[l[queries[i]]];\n        const maxxr = maxr[r[queries[i]]];\n        ret.push(Math.max(Math.max(maxxl, maxxr), d[queries[i]] - 1));\n    }\n\n    return ret;\n};\n```\n```typescript [TS]\n// TypeScript\n\n\nfunction treeQueries(root: TreeNode | null, queries: number[]): number[] {\n    const heights: number[] = new Array(50000).fill(0);\n    const d: number[] = new Array(100001).fill(0);\n    const l: number[] = new Array(100001).fill(0);\n    const r: number[] = new Array(100001).fill(0);\n    let len: number = 0;\n\n    function search(p: TreeNode, h: number): void {\n        d[p.val] = h;\n\n        if (!p.left && !p.right) {\n            heights[len] = h;\n            l[p.val] = r[p.val] = len;\n            len++;\n            return;\n        }\n\n        l[p.val] = len;\n\n        if (p.left) search(p.left, h + 1);\n        if (p.right) search(p.right, h + 1);\n\n        r[p.val] = len - 1;\n    }\n\n    if (!root) return [];\n    search(root, 0);\n\n    const n: number = len;\n    const maxl: number[] = new Array(n).fill(0);\n    const maxr: number[] = new Array(n).fill(0);\n\n    for (let i = 1; i < n; i++) {\n        maxl[i] = Math.max(maxl[i-1], heights[i-1]);\n        maxr[n-i-1] = Math.max(maxr[n-i], heights[n-i]);\n    }\n\n    const ret: number[] = [];\n    const k: number = queries.length;\n\n    for (let i = 0; i < k; i++) {\n        const maxxl: number = maxl[l[queries[i]]];\n        const maxxr: number = maxr[r[queries[i]]];\n        ret.push(Math.max(Math.max(maxxl, maxxr), d[queries[i]] - 1));\n    }\n\n    return ret;\n}\n```\n```rust []\nuse std::cell::RefCell;\nuse std::rc::Rc;\n\nimpl Solution {\n    pub fn tree_queries(root: Option<Rc<RefCell<TreeNode>>>, queries: Vec<i32>) -> Vec<i32> {\n        let mut heights = vec![0; 50000];\n        let mut len = 0;\n        let mut d = vec![0; 100001];\n        let mut l = vec![0; 100001];\n        let mut r = vec![0; 100001];\n\n        fn search(\n            node: Option<Rc<RefCell<TreeNode>>>,\n            h: i32,\n            heights: &mut Vec<i32>,\n            len: &mut usize,\n            d: &mut Vec<i32>,\n            l: &mut Vec<i32>,\n            r: &mut Vec<i32>,\n        ) {\n            if let Some(n) = node {\n                let node = n.borrow();\n                let val = node.val as usize;\n                d[val] = h;\n\n                if node.left.is_none() && node.right.is_none() {\n                    heights[*len] = h;\n                    l[val] = *len as i32;\n                    r[val] = *len as i32;\n                    *len += 1;\n                    return;\n                }\n\n                l[val] = *len as i32;\n\n                search(node.left.clone(), h + 1, heights, len, d, l, r);\n                search(node.right.clone(), h + 1, heights, len, d, l, r);\n\n                r[val] = (*len - 1) as i32;\n            }\n        }\n\n        search(\n            root,\n            0,\n            &mut heights,\n            &mut len,\n            &mut d,\n            &mut l,\n            &mut r,\n        );\n\n        let n = len;\n        let mut maxl = vec![0; n];\n        let mut maxr = vec![0; n];\n\n        for i in 1..n {\n            maxl[i] = maxl[i - 1].max(heights[i - 1]);\n            maxr[n - i - 1] = maxr[n - i].max(heights[n - i]);\n        }\n\n        queries\n            .iter()\n            .map(|&q| {\n                let q = q as usize;\n                let maxxl = maxl[l[q] as usize];\n                let maxxr = maxr[r[q] as usize];\n                maxxl.max(maxxr).max(d[q] - 1)\n            })\n            .collect()\n    }\n}\n```\n```ruby []\ndef tree_queries(root, queries)\n    @heights = Array.new(50000, 0)\n    @len = 0\n    @d = Array.new(100001, 0)\n    @l = Array.new(100001, 0)\n    @r = Array.new(100001, 0)\n    \n    search(root, 0)\n    \n    n = @len\n    maxl = Array.new(n, 0)\n    maxr = Array.new(n, 0)\n    \n    (1...n).each do |i|\n        maxl[i] = [maxl[i-1], @heights[i-1]].max\n        maxr[n-i-1] = [maxr[n-i], @heights[n-i]].max\n    end\n    \n    ret = []\n    queries.each do |query|\n        maxxl = maxl[@l[query]]\n        maxxr = maxr[@r[query]]\n        ret.push([maxxl, maxxr, @d[query]-1].max)\n    end\n    \n    ret\nend\n\ndef search(p, h)\n    @d[p.val] = h\n    \n    if !p.left && !p.right\n        @heights[@len] = h\n        @l[p.val] = @r[p.val] = @len\n        @len += 1\n        return\n    end\n    \n    @l[p.val] = @len\n    \n    search(p.left, h + 1) if p.left\n    search(p.right, h + 1) if p.right\n    \n    @r[p.val] = @len - 1\nend\n\n\n```\n\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)\n\n### Complexity \n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n\n## Explained step by step\n\n---\n\n1. Data Structure Setup:\n```\n# Arrays initialization\nheights = [0] * 50000  # Store leaf node heights\nd = [0] * 100001       # Store depth of each node\nl = [0] * 100001       # Store left boundary index\nr = [0] * 100001       # Store right boundary index\nlen_leaves = 0         # Track number of leaf nodes\n\n```\n\n2. Tree Traversal Function:\n```\ndef search(p: TreeNode, h: int):\n    d[p.val] = h  # Record node depth\n    \n    # Handle leaf node\n    if not p.left and not p.right:\n        heights[len_leaves] = h\n        l[p.val] = r[p.val] = len_leaves\n        len_leaves += 1\n        return\n        \n    l[p.val] = len_leaves  # Set left boundary\n    \n    # Traverse children\n    if p.left: search(p.left, h + 1)\n    if p.right: search(p.right, h + 1)\n    \n    r[p.val] = len_leaves - 1  # Set right boundary\n\n```\n\n3. Maximum Height Arrays Construction:\n```\nn = len_leaves\nmaxl = [0] * n  # Left-to-right maximum heights\nmaxr = [0] * n  # Right-to-left maximum heights\n\n\n# Build prefix and suffix maximums\nfor i in range(1, n):\n    maxl[i] = max(maxl[i-1], heights[i-1])\n    maxr[n-i-1] = max(maxr[n-i], heights[n-i])\n```\n\n4. Query Processing:\n```\nret = []\nfor query in queries:\n    # Find max height excluding queried node\'s subtree\n    maxxl = maxl[l[query]]  # Max height to left\n    maxxr = maxr[r[query]]  # Max height to right\n    ret.append(max(max(maxxl, maxxr), d[query]-1))\n\n```\n- The solution uses DFS to process the tree and record node information\n- For each node, we track:\n    - Its depth\n    - Left and right boundaries of its subtree in the leaf sequence\n    - Heights of leaf nodes\n- We build prefix and suffix maximum arrays to quickly find maximum heights\n- For each query:\n    - We find maximum height outside the queried node\'s subtree\n    - Compare with (depth-1) to get the final result\n\n\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/0bb7edd5-5dde-4671-ab6d-eccd5b5c38c5_1729902242.5845351.png)\n![image.png](https://assets.leetcode.com/users/images/90dc7ced-ba75-4f4a-ad5e-d29377d896bd_1729903813.3417304.png)\n
['Swift', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']