I would strongly recommend against using ref
in normal, managed c# code.
It may occasionally make sense to use out
, but my recommendation for ref
is to save it for calling into unmanaged api's like C libraries.
Your getMaxHeight
method is answering two different questions. This violates the "Single Responsibility Principle" and has some interesting effects, such as
if(!balanced)
return 0;
This isn't true. If your tree is not balanced, that does not mean the max height is 0. Infact, if the max height of your tree was 0 your tree would be balanced.
So those operations need split.
// calculates a max/min tuple based on the given adjacency list
public static (int max, int min) GetHeights(int[][] tree, int current = 0)
{
if (tree[current].Length == 0)
return 1;
int minHeight = int.MaxValue;
int maxHeight = int.MinValue;
foreach (var node in tree[current])
{
int h = GetHeights(tree, node).max;
if (h > maxHeight)
maxHeight = h;
if (h < minHeight)
minHeight = h;
}
return (1 + maxHeight, 1 + minHeight);
}
Now whether a tree is balanced becomes its own method based on the results of the heights.
static bool IsBalanced(int[][] tree)
{
var heights = getHeights(tree);
return heights.max - heights.min <= 1;
}
// note that Math.Abs is not needed because 'max' should be >= 'min',
// otherwise the method is wrong
For large trees you may want to avoid fully computing the min/max heights and return as soon as you know the tree is imbalanced. If you care a lot about that then you could try this alternative
static bool IsBalanced(int[][] sons)
{
bool isBalanced(int[][] tree, int current, out int max)
{
max = 1;
if (tree[current].Length == 0)
return true;
int min = int.MaxValue;
foreach (var node in tree[current])
{
if (!isBalanced(tree, node, out int h))
return false;
if (h > max)
max = h;
if (h < min)
min = h;
if (max - min > 1)
return false;
}
max += 1;
return true;
}
return isBalanced(sons, 0, out int _);
}
This works slightly differently from your code in a couple ways,
It exposes only valid outputs. It contains a 'local function' that has an out param that may be invalid, but the parent function guarantees that can never be misused by not providing access to that outside its own scope. Also by using an out param instead of a ref param we know that each call to the function is independent of the previous state of the parameter, and access from other threads cannot change its value in the middle of our computation - making the method parallelizable.
This method also follows the C# idiom of bool TryThing(TData data, out TResult result)
, examples of which include
int.TryParse
if (int.TryParse("3", out int value))
Console.WriteLine(value);
and ConcurrentQueue<T>.TryDequeue(out T value)
var myQueue = new ConcurrentQueue<int>();
Task.Run(() => myQueue.Enqueue(3));
if (myQueue.TryDequeue(out int value))
Console.WriteLine($"Task ran before dequeue, got value {value}");
Edit
currently, all of these methods will fail if you pass an adjacency list that describes a graph, not a tree. They will fail with a 'stack overflow exception' after exhausting a ton of system resources.
One way to catch that early is to pass along a HashSet of the nodes that have been visited and throw a more descriptive exception as soon as you encounter a duplicate node.
Here is an example with GetHeights
// using System.Collections.Generic; for the HashSet
public static (int max, int min) GetHeights(int[][] tree, int current = 0, HashSet<int> visited = null)
{
visited = visited ?? new HashSet<int>();
if (visited.Contains(current))
throw new InvalidOperationException("Cycle encountered while traversing a 'tree', imposter!");
visited.Add(current);
if (tree[current].Length == 0)
return 1;
int minHeight = int.MaxValue;
int maxHeight = int.MinValue;
foreach (var node in tree[current])
{
// make sure to pass along the hashset
int h = GetHeights(tree, current: node, visited: visited).max;
if (h > maxHeight)
maxHeight = h;
if (h < minHeight)
minHeight = h;
}
return (1 + maxHeight, 1 + minHeight);
}