//Deepdive-V3-377332-Step 1-Code

using System;

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;

    }

}

​

public class Program

{

    public static void Main(string[] args)

    {

      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);

        relatedNodeIds = root.GetRelatedNodeIds(3);

        relatedNodeIds = root.GetRelatedNodeIds(1);

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

        Console.WriteLine($"Related Node IDs for target 5: {string.Join(", ", root.GetRelatedNodeIds(5))}");

        Console.WriteLine($"Related Node IDs for target 3: {string.Join(", ", root.GetRelatedNodeIds(3))}");

        Console.WriteLine($"Related Node IDs for target 1: {string.Join(", ", root.GetRelatedNodeIds(1))}");

        Console.WriteLine($"Related Node IDs for target in null tree: {string.Join(", ", ((Node)null).GetRelatedNodeIds(1))}");

    }

}

​