// A tree is called balanced if a path from a root to any leaf has the same length (=same number of edges to pass).

// Write a function that will check whether a given tree is balanced.

// The tree is specified by int [][]sons array where node 0 is a root and son[i] contains the list of sons of node i.

// Time: O(sons.Length)

using System;

​

public class Program

{

    public static bool IsBalanced(int [][] sons)

    {

        // 1. We'll find the depth of one leaf.

        int node = 0;

        int depth = 0;

        // Invariant: depth contains node depth

        while(sons[node].Length > 0)

        {

            node = sons[node][0];

            depth++;

        }

        // node is leaf

        // 2. We'll make sure any leaf has this depth

        return DepthIs(sons, 0, depth);

    }

​

    // returns true if and only if all descendant leaves of given node have given depth

    // depth >= 0

    public static bool DepthIs(int [][] sons, int node, int depth)

    {

        // any leaf must be at depth 0, any depth 0 must be leaf

        if(depth == 0 || sons[node].Length == 0)

            return depth == 0 && sons[node].Length == 0;

​

        // depth > 0 && non-leaf

        foreach(int child in sons[node])

        {

            if(!DepthIs(sons, child, depth - 1))

                return false;

        }

        // all sons of given node have (depth-1) depth, hence this node is of given depth

        return true;

    }

​

​

    public static void Main()

    {

        int [] LEAF = new int[0];

        int [][] justRoot   = new int[][] { LEAF };

        int [][] fork       = new int[][] { new int[]{ 1, 2},   LEAF,           LEAF };

        int [][] fork4      = new int[][] { new int[]{ 1, 2},   new int [] {3}, LEAF, LEAF };

        int [][] singleLeaf = new int[][] { new int[]{ 1},      new int [] {2}, LEAF };

        Test(justRoot, "root");

        Test(fork, "fork");

        Test(fork4, "fork4");

        Test(singleLeaf, "singleLeaf");

    }

    public static void Test(int [][] sons, string name)

    {

        Console.WriteLine("{0} is {1}", name, IsBalanced(sons) ? "balanced" : "unbalanced");

    }

}