1351 Validate binary tree nodes - C# solution

1351ValidateBinaryTreeNodes.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1361_Validate_binary_tree_nodes
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new Program();
            //var result = test.ValidateBinaryTreeNodes(4, new int[]{1, -1, 3, -1}, new int[]{2, -1, -1, -1}); 
            //var result2 = test.ValidateBinaryTreeNodes(4, new int[]{1, -1, 3, -1}, new int[]{2, 3, -1, -1});
            var result3 = test.ValidateBinaryTreeNodes(2, new int[]{1, 0}, new int[]{-1, -1}); 


        }

        /// <summary>
        /// 1351. Validate binary tree nodes
        /// 1. Binary tree must have a root. This is a node with no incoming edges - that is, the root has no parent; 
        /// 2. Every node other than the root must have exactly one parent; 
        /// 3. The tree must be connected - every node must be reachable from one node ( the root); 
        /// 4. There cannot be a cycle. 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="leftChild"></param>
        /// <param name="rightChild"></param>
        /// <returns></returns>
        public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild)
        {
            var root = findRoot(n, leftChild, rightChild);
            if (root == -1) {
                return false;
            }
        
            // Implement a DFS iteratively with a stack.
            // 
            var seen = new HashSet<int>();
            var stack = new Stack<int>();

            seen.Add(root);
            stack.Push(root);
        
            while (stack.Any()) 
            {
                int node = stack.Pop();
                var children = new int[]{leftChild[node], rightChild[node]};
            
                foreach (var child in children) 
                {
                    if (child != -1) 
                    {
                        if (seen.Contains(child)) 
                        {
                            return false;
                        }
                    
                        stack.Push(child);
                        seen.Add(child);
                    }
                }            
            }
        
            return seen.Count == n;
        }

        /// <summary>
        /// Root node - has no parent
        /// Root node should not show up in left or right array since root node has no parent node. 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        private int findRootAdd(int n, int[] left, int[] right) {
            var children = new HashSet<int>();
            foreach (var node in left) {
                children.Add(node);
            }
        
            foreach (var node in right) {
                children.Add(node);
            }
        
            // Get minimum one - assuming that there is only one root node. 
            for (int i = 0; i < n; i++) {
                if (!children.Contains(i)) 
                {
                    return i;
                }
            }
        
            return -1;
        }

        /// <summary>
        /// Added on Sept. 20, 2023
        /// </summary>
        /// <param name="n"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        private int findRoot(int n, int[] left, int[] right)
        {
            var roots = new HashSet<int>();

            for (int i = 0; i < n; i++)
            {
                roots.Add(i);
            }

            foreach (var node in left)
            {
                roots.Remove(node);                 
            }

            foreach (var node in right)
            {
                roots.Remove(node);
            }

            if (roots.Count == 0 || roots.Count > 1)
            {
                return -1;
            }

            return roots.Min();
        }
    }
}