Monthly Archives: February 2023
C# || How To Find Maximum Difference Between Node and Ancestor In Binary Tree Using C#

The following is a module with functions which demonstrates how to find the maximum difference between node and ancestor in binary tree using C#.
1. Max Ancestor Diff – Problem Statement
Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val – b.val| and a is an ancestor of b.
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Input: root = [1,null,2,null,0,3]
Output: 3
2. Max Ancestor Diff – Solution
The following is a solution which demonstrates how to find the maximum difference between node and ancestor in binary tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 14, 2023 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum difference node and ancestor // ============================================================================ /** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int MaxAncestorDiff(TreeNode root) { if (root == null) { return 0; } return Traverse(root, root.val, root.val); } public int Traverse(TreeNode node, int curMax, int curMin) { // if encounter leaves, return the max-min along the path if (node == null) { return curMax - curMin; } // else, update max and min // and return the max of left and right subtrees curMax = Math.Max(curMax, node.val); curMin = Math.Min(curMin, node.val); int left = Traverse(node.left, curMax, curMin); int right = Traverse(node.right, curMax, curMin); return Math.Max(left, right); } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
7
3
C# || How To Remove Stones To Minimize The Total Using C#

The following is a module with functions which demonstrates how to remove stones to minimize the total using C#.
1. Min Stone Sum – Problem Statement
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:
- Choose any piles[i] and remove floor(piles[i] / 2) stones from it.
Notice that you can apply the operation on the same pile more than once.
Return the minimum possible total number of stones remaining after applying the k operations.
floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
Example 1:
Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.
Example 2:
Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.
2. Min Stone Sum – Solution
The following is a solution which demonstrates how to remove stones to minimize the total.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 1, 2023 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to remove stones to minimize the total // ============================================================================ public class Solution { public int MinStoneSum(int[] piles, int k) { var heap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); int totalSum = 0; foreach (int num in piles) { heap.Enqueue(num, num); totalSum += num; } for (int index = 0; index < k; ++index) { int currentValue = heap.Dequeue(); int removeFromTotal = currentValue / 2; int newValue = currentValue - removeFromTotal; heap.Enqueue(newValue, newValue); totalSum -= removeFromTotal; } return totalSum; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
12
12