Tree -allLeaves, allMiddleNodes, LongestPath

namespace Tree
{
    using System;
    using System.Collections.Generic;
    using System.Text;

    public class Node<T>
    {
        public Node()
        {
            this.Children = new List<Node<T>>();
        }

        public Node(T value) : this()
        {
            this.Value = value;
        }

        public T Value { get; set; }

        public List<Node<T>> Children { get; set; }

        public bool HasParent { get; set; }
    }

    public class Tree<T>
    {
        public Node<T>[] Nodes { get; set; }

        public Node<T> FindRoot()
        {
            var hasParent = new bool[Nodes.Length];

            foreach (var node in Nodes)
            {
                foreach (var child in node.Children)
                {
                    hasParent[(Convert.ToInt32(child.Value))] = true;
                }
            }

            for (int i = 0; i < hasParent.Length; i++)
            {
                if (!hasParent[i])
                {
                    return Nodes[i];
                }
            }

            throw new ArgumentException("nodes", "The tree has no root.");
        }

        public List<Node<T>> FindAllLeaves()
        {
            List<Node<T>> leaves = new List<Node<T>>();

            foreach (var node in Nodes)
            {
                if (node.Children.Count == 0)
                {
                    leaves.Add(node);
                }
            }

            return leaves;
        }

        public List<Node<T>> FindAllMiddleNodes()
        {
            List<Node<T>> middleNodes = new List<Node<T>>();

            foreach (var node in Nodes)
            {
                if (node.HasParent && node.Children.Count > 0)
                {
                    middleNodes.Add(node);
                }
            }

            return middleNodes;
        }

        public int FindLongestPath(Node<T> root)
        {
            if (root.Children.Count == 0)
            {
                return 0;
            }

            int maxPath = 0;
            foreach (var node in root.Children)
            {
                maxPath = Math.Max(maxPath, FindLongestPath(node));
            }

            return maxPath + 1;
        }
    }

    public class TreeProgram
    {
        public static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            var nodes = new Node<int>[n];

            for (int i = 0; i < n; i++)
            {
                nodes[i] = new Node<int>(i);
            }

            for (int i = 1; i <= n - 1; i++)
            {
                string edgeAsString = Console.ReadLine();
                var edgeParts = edgeAsString.Split(' ');

                int parentId = int.Parse(edgeParts[0]);
                int childId = int.Parse(edgeParts[1]);

                nodes[parentId].Children.Add(nodes[childId]);
                nodes[childId].HasParent = true;
            }

            Tree<int> tree = new Tree<int>();
            tree.Nodes = nodes;

            // 1. Find the root
            var root = tree.FindRoot();
            Console.WriteLine("The root of the tree is: {0}", root.Value);

            // 2. Find all leaves
            List<Node<int>> leaves = tree.FindAllLeaves();
            Console.Write("Leaves: ");
            Console.WriteLine(PrintNodes(leaves));

            // 3. Find all middle nodes
            var middleNodes = tree.FindAllMiddleNodes();
            Console.Write("Middle nodes: ");
            Console.WriteLine(PrintNodes(middleNodes));

            // 4. Find the longest path from the root
            var longestPath = tree.FindLongestPath(tree.FindRoot());
            Console.WriteLine("Number of levels: {0}", longestPath + 1);
        }

        private static string PrintNodes(List<Node<int>> nodes)
        {
            StringBuilder output = new StringBuilder();
            foreach (var node in nodes)
            {
                output.AppendFormat("{0} ", node.Value);
            }

            return output.ToString();
        }
    }
}