using System;

using NUnit.Framework;

using System.Collections.Generic;

using System.Linq;

​

​

public class Node

{

    public int Id { get; set; }

    public List<int> ChildrenIds { get; set; }

​

    public Node(int id, List<int> childrenIds = null)

    {

        Id = id;

        ChildrenIds = childrenIds ?? new List<int>();

    }

}

​

public static class TreeExtensions

{

     public static List<int> GetRelatedNodeIds(this Node root, int targetNodeId)

    {

        if(root == null)

        {

            return new List<int>();

        }

​

        var targetNodePath = FindPathToNode(root, targetNodeId);

        if (targetNodePath == null)

        {

             return new List<int>(); // Target node not found in the tree

        }

​

        var relatedNodeIds = new HashSet<int>();

        //Add Ancestors

        foreach(var nodeId in targetNodePath)

        {

            relatedNodeIds.Add(nodeId);

        }

​

        //Add Descendants of target and its ancestors

        foreach (var ancestorId in targetNodePath)

        {

           var ancestor = FindNodeById(root, ancestorId);

           if(ancestor != null)

           {

             relatedNodeIds.UnionWith(GetAllDescendantIds(ancestor));

           }

        }

​

        return relatedNodeIds.ToList();

    }

​

     private static List<int> FindPathToNode(Node root, int targetNodeId)

    {

        if (root == null)

        {

            return null;

        }

​

        if (root.Id == targetNodeId)

        {

            return new List<int> { root.Id };

        }

         foreach(var childId in root.ChildrenIds)

         {

           var child = FindNodeById(root, childId);

           var path = FindPathToNode(child, targetNodeId);

           if(path != null)

           {

                path.Insert(0, root.Id);

                return path;

           }

         }

​

         return null;

    }

​

    private static Node FindNodeById(Node root, int nodeId)

    {

      if(root == null)

      {

        return null;

      }

​

      if(root.Id == nodeId)

      {

        return root;

      }

​

      foreach(var childId in root.ChildrenIds)

      {

         var child = FindNodeById(root, childId);

         if(child != null)

          {

              return child;

          }

      }

​

      return null;

    }

​

    private static HashSet<int> GetAllDescendantIds(Node node)

    {

      var descendants = new HashSet<int>();

      if(node == null)

      {

         return descendants;

      }

      descendants.Add(node.Id);

      foreach(var childId in node.ChildrenIds)

      {

        var child = FindNodeById(node, childId);

        if(child != null)

        {

            descendants.UnionWith(GetAllDescendantIds(child));

        }

      }

​

      return descendants;

    }

}

​

​

[TestFixture]

public class TreeTests

{

    [Test]

    public void TestRelatedNodes_TargetIsLeafNode()

    {

        var root = new Node(1, new List<int> { 2, 3, 4 });

        root.ChildrenIds.Add(2);

        root.ChildrenIds.Add(3);

        root.ChildrenIds.Add(4);

        var node2 = new Node(2, new List<int>{5,6});

        var node3 = new Node(3, new List<int>{7});

        var node4 = new Node(4);

        var node5 = new Node(5);

        var node6 = new Node(6);

        var node7 = new Node(7);

​

        // Add Children to the tree

        var nodes = new List<Node>() { root, node2, node3, node4, node5, node6, node7 };

         var relatedNodeIds = root.GetRelatedNodeIds(5);

         CollectionAssert.AreEquivalent(new List<int>{1,2,5,6}, relatedNodeIds);

    }

​

​

    [Test]

    public void TestRelatedNodes_TargetIsMiddleNode()

    {

         var root = new Node(1, new List<int> { 2, 3, 4 });

        root.ChildrenIds.Add(2);

        root.ChildrenIds.Add(3);

        root.ChildrenIds.Add(4);

        var node2 = new Node(2, new List<int>{5,6});

        var node3 = new Node(3, new List<int>{7});

        var node4 = new Node(4);

        var node5 = new Node(5);

        var node6 = new Node(6);

        var node7 = new Node(7);

​

        // Add Children to the tree

        var nodes = new List<Node>() { root, node2, node3, node4, node5, node6, node7 };

        var relatedNodeIds = root.GetRelatedNodeIds(3);

        CollectionAssert.AreEquivalent(new List<int> { 1, 3, 7 }, relatedNodeIds);

    }

​

    [Test]

     public void TestRelatedNodes_TargetIsRootNode()

    {

        var root = new Node(1, new List<int> { 2, 3, 4 });

        root.ChildrenIds.Add(2);

        root.ChildrenIds.Add(3);

        root.ChildrenIds.Add(4);

        var node2 = new Node(2, new List<int>{5,6});

        var node3 = new Node(3, new List<int>{7});

        var node4 = new Node(4);

        var node5 = new Node(5);

        var node6 = new Node(6);

        var node7 = new Node(7);

​

        // Add Children to the tree

        var nodes = new List<Node>() { root, node2, node3, node4, node5, node6, node7 };

        var relatedNodeIds = root.GetRelatedNodeIds(1);

         CollectionAssert.AreEquivalent(new List<int> { 1, 2, 3, 4, 5, 6, 7 }, relatedNodeIds);

    }

​

    [Test]

    public void TestRelatedNodes_TargetNodeDoesNotExist()

    {

        var root = new Node(1, new List<int> { 2, 3, 4 });

        root.ChildrenIds.Add(2);

        root.ChildrenIds.Add(3);

        root.ChildrenIds.Add(4);

        var node2 = new Node(2, new List<int>{5,6});

        var node3 = new Node(3, new List<int>{7});

        var node4 = new Node(4);

        var node5 = new Node(5);

        var node6 = new Node(6);

        var node7 = new Node(7);

​

        // Add Children to the tree

        var nodes = new List<Node>() { root, node2, node3, node4, node5, node6, node7 };

​

        var relatedNodeIds = root.GetRelatedNodeIds(9);

        Assert.IsEmpty(relatedNodeIds);

    }

​

​

    [Test]

     public void TestRelatedNodes_EmptyTree()

    {

        var relatedNodeIds = ((Node)null).GetRelatedNodeIds(1);

         Assert.IsEmpty(relatedNodeIds);

    }

​

    [Test]

    public void TestRelatedNodes_SingleNodeTree()

    {

         var root = new Node(1);

         var relatedNodeIds = root.GetRelatedNodeIds(1);

          CollectionAssert.AreEquivalent(new List<int> {1}, relatedNodeIds);

​

         var relatedNodeIds_NotFound = root.GetRelatedNodeIds(2);

         Assert.IsEmpty(relatedNodeIds_NotFound);

​

    }

​

​

    [Test]

      public void TestRelatedNodes_UnbalancedTree()

    {

        var root = new Node(1, new List<int>() {2});

        var node2 = new Node(2, new List<int>() {3});

        var node3 = new Node(3, new List<int>() {4});

        var node4 = new Node(4);

​

        var nodes = new List<Node>() { root, node2, node3, node4 };

​

​

        var relatedNodeIds = root.GetRelatedNodeIds(3);

        CollectionAssert.AreEquivalent(new List<int> {1, 2, 3, 4}, relatedNodeIds);

​

        relatedNodeIds = root.GetRelatedNodeIds(4);

        CollectionAssert.AreEquivalent(new List<int> {1,2,3,4}, relatedNodeIds);

         relatedNodeIds = root.GetRelatedNodeIds(1);

         CollectionAssert.AreEquivalent(new List<int> {1, 2, 3, 4}, relatedNodeIds);

    }

}

​

public class Program

{

    public static void Main(string[] args)

    {

        Console.WriteLine(" ");

        Console.WriteLine("-------------- STARTING UNIT TESTING ---------------");

        new NUnitLite.AutoRun().Execute(["--noc" ]);

    }

}

​