0
\$\begingroup\$

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));
    }
}
\$\endgroup\$
2
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ For some reasons I cannot figure out my compiler complains while using the static bool IsBalanced(int[][] sons). Could you please include your Main() method? \$\endgroup\$ – FunnyBuzer May 16 '18 at 23:47
  • \$\begingroup\$ I used exactly the same Main method you posted to test it. What compiler/build-tools are you using? Nested functions are a reasonably recent feature so tools like Mono or Unity (...which uses Mono) may not support it. To fix that you could just move the nested isBalanced out of its parent function and make it private static or set your project settings to a recent tooling that supports C# 7 \$\endgroup\$ – Kelson Ball May 16 '18 at 23:51
  • \$\begingroup\$ I use an online compiler. Actually it complains about return isBalanced(sons, 0, out int _); and if (!isBalanced(tree, node, out int h)) \$\endgroup\$ – FunnyBuzer May 16 '18 at 23:59
  • \$\begingroup\$ in fact, symbol _ is not recognised \$\endgroup\$ – FunnyBuzer May 17 '18 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.