< Summary

Information
Class: LeetCode.Algorithms.HeightOfBinaryTreeAfterSubtreeRemovalQueries.HeightOfBinaryTreeAfterSubtreeRemovalQueriesDepthFirstSearch
Assembly: LeetCode
File(s): D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\HeightOfBinaryTreeAfterSubtreeRemovalQueries\HeightOfBinaryTreeAfterSubtreeRemovalQueriesDepthFirstSearch.cs
Line coverage
100%
Covered lines: 92
Uncovered lines: 0
Coverable lines: 92
Total lines: 193
Line coverage: 100%
Branch coverage
100%
Covered branches: 24
Total branches: 24
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
TreeQueries(...)100%11100%
LeftToRight(...)100%66100%
RightToLeft(...)100%66100%
GetNodesCount(...)100%1010100%
GetAnswer(...)100%22100%

File(s)

D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\HeightOfBinaryTreeAfterSubtreeRemovalQueries\HeightOfBinaryTreeAfterSubtreeRemovalQueriesDepthFirstSearch.cs

#LineLine coverage
 1// --------------------------------------------------------------------------------
 2// Copyright (C) 2026 Eugene Eremeev (also known as Yevhenii Yeriemeieiv).
 3// All Rights Reserved.
 4// --------------------------------------------------------------------------------
 5// This software is the confidential and proprietary information of Eugene Eremeev
 6// (also known as Yevhenii Yeriemeieiv) ("Confidential Information"). You shall not
 7// disclose such Confidential Information and shall use it only in accordance with
 8// the terms of the license agreement you entered into with Eugene Eremeev (also
 9// known as Yevhenii Yeriemeieiv).
 10// --------------------------------------------------------------------------------
 11
 12using LeetCode.Core.Models;
 13
 14namespace LeetCode.Algorithms.HeightOfBinaryTreeAfterSubtreeRemovalQueries;
 15
 16/// <inheritdoc />
 17public sealed class HeightOfBinaryTreeAfterSubtreeRemovalQueriesDepthFirstSearch :
 18    IHeightOfBinaryTreeAfterSubtreeRemovalQueries
 19{
 20    /// <summary>
 21    ///     Time complexity - O(n + m), where n is the number of nodes and m is the number of queries
 22    ///     Space complexity - O(n), where n is the number of nodes
 23    /// </summary>
 24    /// <param name="root"></param>
 25    /// <param name="queries"></param>
 26    /// <returns></returns>
 27    public int[] TreeQueries(TreeNode root, int[] queries)
 328    {
 329        var nodesCount = GetNodesCount(root);
 30
 331        Span<int> heights = stackalloc int[nodesCount + 1];
 32
 333        LeftToRight(root, heights);
 34
 335        RightToLeft(root, heights);
 36
 337        return GetAnswer(queries, heights);
 338    }
 39
 40    /// <summary>
 41    ///     Time complexity - O(n), where n is the number of nodes
 42    ///     Space complexity - O(n), where n is the number of nodes
 43    /// </summary>
 44    /// <param name="root"></param>
 45    /// <param name="heights"></param>
 46    private static void LeftToRight(TreeNode root, Span<int> heights)
 347    {
 348        var maxHeight = 0;
 49
 350        var nodesStack = new Stack<(TreeNode Node, int CurrentHeight)>();
 51
 352        nodesStack.Push((root, -1));
 53
 2454        while (nodesStack.Count > 0)
 2155        {
 2156            var (node, currentHeight) = nodesStack.Pop();
 57
 2158            var nodeValue = node.val;
 59
 2160            heights[nodeValue] = Math.Max(Math.Max(maxHeight, currentHeight), heights[nodeValue]);
 61
 2162            var nextHeight = currentHeight + 1;
 63
 2164            maxHeight = Math.Max(maxHeight, nextHeight);
 65
 2166            var rightNode = node.right;
 67
 2168            if (rightNode != null)
 969            {
 970                nodesStack.Push((rightNode, nextHeight));
 971            }
 72
 2173            var leftNode = node.left;
 74
 2175            if (leftNode != null)
 976            {
 977                nodesStack.Push((leftNode, nextHeight));
 978            }
 2179        }
 380    }
 81
 82    /// <summary>
 83    ///     Time complexity - O(n), where n is the number of nodes
 84    ///     Space complexity - O(n), where n is the number of nodes
 85    /// </summary>
 86    /// <param name="root"></param>
 87    /// <param name="heights"></param>
 88    private static void RightToLeft(TreeNode root, Span<int> heights)
 389    {
 390        var maxHeight = 0;
 91
 392        var nodesStack = new Stack<(TreeNode Node, int CurrentHeight)>();
 93
 394        nodesStack.Push((root, -1));
 95
 2496        while (nodesStack.Count > 0)
 2197        {
 2198            var (node, currentHeight) = nodesStack.Pop();
 99
 21100            var nodeValue = node.val;
 101
 21102            heights[nodeValue] = Math.Max(Math.Max(maxHeight, currentHeight), heights[nodeValue]);
 103
 21104            var nextHeight = currentHeight + 1;
 105
 21106            maxHeight = Math.Max(maxHeight, nextHeight);
 107
 21108            var leftNode = node.left;
 109
 21110            if (leftNode != null)
 9111            {
 9112                nodesStack.Push((leftNode, nextHeight));
 9113            }
 114
 21115            var rightNode = node.right;
 116
 21117            if (rightNode != null)
 9118            {
 9119                nodesStack.Push((rightNode, nextHeight));
 9120            }
 21121        }
 3122    }
 123
 124    /// <summary>
 125    ///     Time complexity - O(n), where n is the number of nodes
 126    ///     Space complexity - O(1)
 127    /// </summary>
 128    /// <param name="root"></param>
 129    /// <returns></returns>
 130    private static int GetNodesCount(TreeNode? root)
 3131    {
 3132        var nodesCount = 0;
 133
 3134        var current = root;
 135
 33136        while (current != null)
 30137        {
 30138            if (current.left == null)
 12139            {
 12140                nodesCount++;
 141
 12142                current = current.right;
 12143            }
 144            else
 18145            {
 18146                var previous = current.left;
 147
 24148                while (previous.right != null && previous.right != current)
 6149                {
 6150                    previous = previous.right;
 6151                }
 152
 18153                if (previous.right == null)
 9154                {
 9155                    previous.right = current;
 156
 9157                    current = current.left;
 9158                }
 159                else
 9160                {
 9161                    previous.right = null;
 162
 9163                    nodesCount++;
 164
 9165                    current = current.right;
 9166                }
 18167            }
 30168        }
 169
 3170        return nodesCount;
 3171    }
 172
 173    /// <summary>
 174    ///     Time complexity - O(m), where m is the number of queries
 175    ///     Space complexity - O(1)
 176    /// </summary>
 177    /// <param name="queries"></param>
 178    /// <param name="heights"></param>
 179    /// <returns></returns>
 180    private static int[] GetAnswer(int[] queries, ReadOnlySpan<int> heights)
 3181    {
 3182        var queriesLength = queries.Length;
 183
 26184        for (var i = 0; i < queriesLength; i++)
 10185        {
 10186            var query = queries[i];
 187
 10188            queries[i] = heights[query];
 10189        }
 190
 3191        return queries;
 3192    }
 193}
Generated by: ReportGenerator 5.5.4.0
4/1/2026 - 8:25:10 AM
GitHub | reportgenerator.io

Methods/Properties

TreeQueries(LeetCode.Core.Models.TreeNode,System.Int32[])
LeftToRight(LeetCode.Core.Models.TreeNode,System.Span`1<System.Int32>)
RightToLeft(LeetCode.Core.Models.TreeNode,System.Span`1<System.Int32>)
GetNodesCount(LeetCode.Core.Models.TreeNode)
GetAnswer(System.Int32[],System.ReadOnlySpan`1<System.Int32>)