Balanced tree in C#

Question

Given the adjacency list to represent a tree from the root (node 0) to the leaves, I want to write a function that takes this adjacency list as a parameter and return whether the tree is balanced. Definition: a tree is said to be balanced if a path from a root to any leaf has the same length.

I should be grateful if you could share your thoughts about this function.

using System;
    public class MainClass 
    {
    static bool isBalanced(int[][] sons) 
    {
        bool balanced = true;
        getMaxHeight(sons, 0, ref balanced);
        return balanced;
    }

    static int getMaxHeight(int[][] sons, int startNode, ref bool balanced) 
    {            
        if(!balanced)
            return 0;

        int[] children = sons[startNode];
        if(children.Length == 0) 
            return 1; // balanced should not be changed

        int minHeight = int.MaxValue;
        int maxHeight = int.MinValue;

        foreach (int node in children) 
        {
            int h = getMaxHeight(sons, node, ref balanced);
            if(h > maxHeight)
                maxHeight = h;

            if(h < minHeight)
                minHeight = h;   
        }

        if(Math.Abs(maxHeight - minHeight) >= 2) 
            balanced = false;

        return 1 + maxHeight;
    }
    //Time Complexity: O(sons.Length) since each node is only visisted once

    public static void Main (string[] args) 
    {
        int[][] sons = new int[6][];

        sons[0] = new int[] { 1, 2, 4 };
        sons[1] = new int[] { };
        sons[2] = new int[] { 3, 5};
        sons[3] = new int[] { };
        sons[4] = new int[] { };
        sons[5] = new int[] { };

        Console.WriteLine (isBalanced(sons));
    }
}

Answer 1

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);
}