Creating a recursive list of objects C#

Question

Hi I have a class like this:

public class Node
{
    public Node();

    public long NodeId { get; set; }

    public int? LevelId { get; set; }

    public ICollection<Node> Children { get; set; }
}

I have managed to recursively add Children to children. Now, printing the data is the problem.

Referencing from this: Recursive List Flattening this returns a flattened list.

private IEnumerable<Node> GetNodes()
{
  // Create a 3-level deep hierarchy of nodes
  Node[] nodes = new Node[]
    {
      new Node 
      { 
        NodeId = 1, 
        LevelId = 1, 
        Children = new Node[]
        {
          new Node { NodeId = 2, LevelId = 2, Children = new Node[] {} },
          new Node
          {
            NodeId = 3,
            LevelId = 2,
            Children = new Node[]
            {
              new Node { NodeId = 4, LevelId = 3, Children = new Node[] {} },
              new Node { NodeId = 5, LevelId = 3, Children = new Node[] {} }
            }
          }
        }
      },
      new Node { NodeId = 6, LevelId = 1, Children = new Node[] {} }
    };
  return nodes;
}

However, need data in this format. example.

NodeId | LevelId | ChildNodeId | ChildLeveld | ChildNodeId | ChildLevelId 
1      | 1       | 2           |  2
1      | 1       | 3           |  2          | 4           | 3
1      | 1       | 3           |  2          | 5           | 3

like:

currently I have a class with nodeid and levelid. how can I dynamically create other childnodes and return as a collection of objects.

public Class New Class 
{
  public int NodeId {get;set;}
  public int LevelId {get;set;}
  public Dictionary<string, object> {get;set;}

  // create dynamic childId and levelId in the dictionary
}

Answer 1

You leaf node should be null and not an empty list so you can test for null instead of a count of zero. You also do not need to columns for each level. See code below

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Data;

namespace ConsoleApplication4
{
    class Program
    {

        static void Main(string[] args)
        {
            Node root = new Node();
            root.setRoot();
            root.BuildTable();
            root.PrintTable();
            Console.ReadLine();
        }
    }
    public class Node
    {
        DataTable dt = new DataTable();
        int maxDepth = 0;
        List<Node> nodes { get; set; }
        public long NodeId { get; set; }
        public int LevelId { get; set; }
        public List<Node> Children { get; set; }

        public void setRoot()
        {
            nodes = GetNodes().ToList();
        }
        public void GetMaxDepth()
        {
            maxDepth = GetMaxDepthRecursive(nodes, 0);
        }
        public int GetMaxDepthRecursive(List<Node> nodes, int depth)
        {
            int returnDepth = depth + 1;
            foreach (Node child in nodes)
            {
                if (child.Children != null)
                {
                    int newDepth = GetMaxDepthRecursive(child.Children, depth + 1);
                    if (newDepth > returnDepth) returnDepth = newDepth;
                }
            }
            return returnDepth;
        }


        private IEnumerable<Node> GetNodes()
        {
            // Create a 3-level deep hierarchy of nodes
            Node[] nodes = new Node[]
            {
                new Node 
                { 
                    NodeId = 1, 
                    LevelId = 1, 
                    Children = new List<Node>()
                    {
                        new Node { NodeId = 2, LevelId = 2, Children = null },
                        new Node
                        {
                            NodeId = 3,
                            LevelId = 2,
                            Children = new List<Node>()
                            {
                                new Node { NodeId = 4, LevelId = 3, Children = null },
                                new Node { NodeId = 5, LevelId = 3, Children = null }
                            }
                        }
                    }
                },
              new Node { NodeId = 6, LevelId = 1, Children = null }
            };
            return nodes;
        }
        public void GetTableRowsRecursive(List<Node> nodes, List<KeyValuePair<int,long>> parents)
        {
            string columnName = "";
            foreach (Node node in nodes)
            {
                if (node.Children == null)
                {
                    DataRow newRow = dt.Rows.Add();
                    if (parents != null)
                    {
                        foreach (KeyValuePair<int, long> parent in parents)
                        {
                            columnName = string.Format("Level {0} Node ID", parent.Key.ToString());
                            newRow[columnName] = parent.Value;
                        }
                    }
                    columnName = string.Format("Level {0} Node ID", node.LevelId);
                    newRow[columnName] = node.NodeId;
                }
                else
                {
                    List<KeyValuePair<int, long>> newParents = new List<KeyValuePair<int, long>>();
                    if(parents != null) newParents.AddRange(parents);
                    newParents.Add(new KeyValuePair<int,long>(node.LevelId, node.NodeId));
                    GetTableRowsRecursive(node.Children, newParents);
                }

            }

        }
        public void BuildTable()
        {
            GetMaxDepth();
            dt = new DataTable();
            for (int i = 1; i <= maxDepth; i++)
            {
                string columnName = string.Format("Level {0} Node ID", i.ToString());
                dt.Columns.Add(columnName, typeof(int));
            }
            GetTableRowsRecursive(nodes, null);
        }
        public void PrintTable()
        {
            string line = string.Join("   ",dt.Columns.Cast<DataColumn>().Select(x => string.Format("{0,-15}",x.ColumnName)));
            Console.WriteLine(line);
            foreach (DataRow row in dt.AsEnumerable())
            {
                line = string.Join("   ", row.ItemArray.Select(x => string.Format("{0,-15}", x)));
                Console.WriteLine(line);
            }
        }

    }
}

---

Output

Answer 2

What you're looking for is a recursive traversal of a tree. You track breadcrumbs along the way and build a new path to add to the results whenever you encounter a leaf node (one with no children).

In this output, each row shows ID and Depth separated by a comma, with each node in the path to the leaf node separated by the pipe symbol:

1,1 | 2,2
1,1 | 3,2 | 4,3
1,1 | 3,2 | 5,3
6,1
Press Enter to Quit...

Here is the code that generated that output:

class Program
{

    public static void Main()
    {
        IEnumerable<Node> nodes = GetNodes(); // your test data
        List<List<NodeData>> results = new List<List<NodeData>>(); // will store results
        foreach (Node n in nodes)
        {
            n.Traverse(null, results); // start at each root node
        }

        // output the path to each leaf node from results
        // *you can obviously format this differently to your liking
        foreach(List<NodeData> path in results)
        {
            Console.WriteLine(String.Join(" | ", path.Select(p => p.ToString()).ToArray()));
        }
        Console.WriteLine("Press Enter to Quit...");
        Console.ReadLine();
    }

    private static IEnumerable<Node> GetNodes()
    {
        // Create a 3-level deep hierarchy of nodes
        Node[] nodes = new Node[]
        {
              new Node
              {
                    NodeId = 1,
                    LevelId = 1,
                    Children = new Node[]
                    {
                          new Node { NodeId = 2, LevelId = 2, Children = new Node[] {} },
                          new Node
                          {
                                NodeId = 3,
                                LevelId = 2,
                                Children = new Node[]
                                {
                                      new Node { NodeId = 4, LevelId = 3, Children = new Node[] {} },
                                      new Node { NodeId = 5, LevelId = 3, Children = new Node[] {} }
                                }
                          }
                    }
              },
              new Node
              {
                  NodeId = 6,
                  LevelId = 1,
                  Children = new Node[] {}
              }
        };
        return nodes;
    }

}

public class Node
{
    public Node() {}

    public long NodeId { get; set; }

    public int? LevelId { get; set; }

    public ICollection<Node> Children { get; set; }

    public override string ToString()
    {
        return NodeId.ToString();
    }

    public void Traverse(List<Node> crumbs, List<List<NodeData>> results)
    {
        if (crumbs == null) { crumbs = new List<Node>(); }
        crumbs.Add(this);
        if (Children.Count == 0)
        {
            List<NodeData> path = new List<NodeData>();
            foreach(Node n in crumbs)
            {
                path.Add(new NodeData() { NodeId = n.NodeId, LevelId = n.LevelId.Value });
            }
            results.Add(path);
        }
        else
        {
            foreach (Node n in Children)
            {
                n.Traverse(crumbs, results);
            }
        }
        crumbs.Remove(this);
    }

}

public class NodeData
{
    public long NodeId { get; set; }
    public int LevelId { get; set; }

    public override string ToString()
    {
        return NodeId + "," + LevelId;
    }
}