Search Hierarchical Data Using Linq

Question

I am trying to search hierarchical data based on the advice provided in this question How to search Hierarchical Data with Linq . However, I am stuck.

var NodeTypes = new NodeType[] {
    new NodeType{
      NodeTypeDescription = "First Level",
      Item = new CodeType(){  CodeValue = "01" },
      Node = new NodeType[]{
        new NodeType{
          NodeTypeDescription = "First Child Level 0101",
          Item = new CodeType(){  CodeValue = "0101" },
          Node = new NodeType[]{
            new NodeType{
              NodeTypeDescription = "Target Level Description",
              Item = new ModelType(){ ModelId = 1234, ModelTitle = "Target-1234" },
              Node = null
            }
          }
       },
       new NodeType{
         NodeTypeDescription = "First Child Level 0102",
         Item = new CodeType(){  CodeValue = "0102" },
         Node = new NodeType[]{
           new NodeType{
             NodeTypeDescription = "Target Level Description",
             Item = new ModelType(){ ModelId = 2345, ModelTitle = "Target-2345" },
            Node = null
           }
         }
       }
    }
   },
   new NodeType{
     NodeTypeDescription = "Second Level",
     Item = new CodeType(){  CodeValue = "02" },
     Node = new NodeType[]{
       new NodeType{
         NodeTypeDescription = "Second Child Level 0201",
         Item = new CodeType(){  CodeValue = "0201" },
         Node = new NodeType[]{
           new NodeType{
             NodeTypeDescription = "Second Child Level 020101",
             Item = new CodeType(){  CodeValue = "020101" },
             Node = new NodeType[]{
               new NodeType{
                 NodeTypeDescription = "Target Level Description",
                 Item = new ModelType(){ ModelId = 2345, ModelTitle = "Target-2345" },
                 Node = null
               }
             }
           }
         }
       },
       new NodeType{
         NodeTypeDescription = "Second Child Level 0202",
         Item = new CodeType(){  CodeValue = "0202" },
         Node = new NodeType[]{
           new NodeType{
             NodeTypeDescription = "Target Level Description",
             Item = new ModelType(){ ModelId = 3456, ModelTitle = "Target-3456" },
             Node = null
           }
         }
       }
     }
   }
 };

I have placed the sample code here.

public static class Extensions
{
    public static IEnumerable<T> Flatten<T>(this T source, Func<T, IEnumerable<T>> selector)
    {
        return selector(source).SelectMany(c => Flatten(c, selector))
                               .Concat(new[] { source });
    }
}

public class ModelType
{
    public string ModelTitle;
    public long ModelId;
}

public class CodeType
{
    public string CodeValue;
}

public class NodeType
{
    public string NodeTypeDescription { get; set; }
    public object Item { get; set; }
    public NodeType[] Node { get; set; }
}

public class Program
{
    public static void Main()
    {

        var NodeTypes = new NodeType[] {
                new NodeType{
                         NodeTypeDescription = "First Level",
                         Item = new CodeType(){  CodeValue = "01" },
                         Node = new NodeType[]{
                            new NodeType{
                                NodeTypeDescription = "First Child Level 0101",
                                Item = new CodeType(){  CodeValue = "0101" },
                                Node = new NodeType[]{
                                    new NodeType{
                                        NodeTypeDescription = "Target Level Description",
                                        Item = new ModelType(){ ModelId = 1234, ModelTitle = "Target-1234" },
                                        Node = null
                                    }
                                }
                            },
                            new NodeType{
                                NodeTypeDescription = "First Child Level 0102",
                                Item = new CodeType(){  CodeValue = "0102" },
                                Node = new NodeType[]{
                                    new NodeType{
                                        NodeTypeDescription = "Target Level Description",
                                        Item = new ModelType(){ ModelId = 2345, ModelTitle = "Target-2345" },
                                        Node = null
                                    }
                                }
                            }
                         }
                },
                new NodeType{
                         NodeTypeDescription = "Second Level",
                         Item = new CodeType(){  CodeValue = "02" },
                         Node = new NodeType[]{
                            new NodeType{
                                NodeTypeDescription = "Second Child Level 0201",
                                Item = new CodeType(){  CodeValue = "0201" },
                                Node = new NodeType[]{
                                    new NodeType{
                                        NodeTypeDescription = "Second Child Level 020101",
                                        Item = new CodeType(){  CodeValue = "020101" },
                                        Node = new NodeType[]{
                                            new NodeType{
                                                NodeTypeDescription = "Target Level Description",
                                                Item = new ModelType(){ ModelId = 2345, ModelTitle = "Target-2345" },
                                                Node = null
                                            }
                                        }
                                    }
                                }
                            },
                            new NodeType{
                                NodeTypeDescription = "Second Child Level 0202",
                                Item = new CodeType(){  CodeValue = "0202" },
                                Node = new NodeType[]{
                                    new NodeType{
                                        NodeTypeDescription = "Target Level Description",
                                        Item = new ModelType(){ ModelId = 3456, ModelTitle = "Target-3456" },
                                        Node = null
                                    }
                                }
                            }
                         }
                }
            };

        var result = NodeTypes[0].Flatten(x => x.Node).Where(y => ((ModelType)(y.Item)).ModelId == 2345);
    }
}

I don't think this is right

var result = NodeTypes[0].Flatten(x => x.Node).Where(y => ((ModelType)(y.Item)).ModelId == 2345);

as I want to search all nodes and the target node could be at any depth,

Another question ...

After flattening the hierarchy, how can we also get the details from the parent or sibling. Say, I want to extract the codeValue from its parent's sibling Item node.

var result2 = DepthFirst<NodeType>(NodeTypes, n => n.Node).ToList(); 
var result1 = result2.Where(n => n.Item.GetType() == typeof(ModelType) && ((ModelType)n.Item).ModelId == 2345).ToList();

[Please don't post code, exceptions, or results as images](https://meta.stackoverflow.com/questions/285551/why-not-upload-images-of-code-errors-when-asking-a-question). They can't be copied (partly) for answering and their "text" won't appear in search engines. Also, the code should be part of the question text, not an external source. — Gert Arnold, Jul 22 '22 at 11:56

score 1 · Accepted Answer · answered Jul 22 '22 at 12:27

I prefer to use a extension method to iterate the tree, something like:

        public static IEnumerable<T> DepthFirst<T>(IEnumerable<T> roots, Func<T, IEnumerable<T>> selector)
        {
            var stack = new Stack<T>();
            foreach (var r in roots)
            {
                stack.Push(r);
            }
            while (stack.Count > 0)
            {
                var current = stack.Pop();
                yield return current;
                foreach (var child in selector(current))
                {
                    stack.Push(child);
                }
            }
        }

Called like DepthFirst(nodeTypes, n => n.Node), and produces a iterator of all nodes in the tree, regardless of depth. The Flatten method from the linked answer should probably also work, since it is recursive, but it will likely create a tree of linq iterators, so I would expect it to have substantial overhead when doing the iteration.

Then it should simply be an issue if filtering out the nodes you are searching for:

DepthFirst(nodeTypes, n => n.Node).Where(n => n.Item.ModelId == 2345);

If you want to do a BreadthFirst search instead you simply replace the stack with a queue. If you can have cycles in your graph you need to add a hashSet of visited nodes, and check this before traversing each node.

had to check if selector(current) was not null as it would be so in the terminal node, otherwise perfect. — InquisitiveLad, Jul 26 '22 at 00:24
Sorry, another question - asking it here because it is related to this one. After flattening the hierarchy, how can we also get the details from the parent or sibling. Say, I want to extract the codeValue from its parent's sibling Item node. var result2 = DepthFirst(NodeTypes, n => n.Node).ToList(); var result1 = result2.Where(n => n.Item.GetType() == typeof(ModelType) && ((ModelType)n.Item).ModelId == 2345).ToList(); — InquisitiveLad, Jul 26 '22 at 00:54
@InquisitiveLad You can keep track of the parent by using a pair, i.e. `Stack<(T Parent, T Node)>`. And corresponding changes when popping/pushing values. Once you have the parent you can get siblings. But if you want to do any more complex calculation you might be better doing some kind of mapping of the tree. — JonasH, Jul 26 '22 at 07:47

score 1 · Answer 2 · answered Jul 22 '22 at 13:05

You have to write your own flatten method like this

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

namespace ConsoleApplication35
{
    class Program
    {
        static void Main(string[] args)
        {
            NodeType root = new NodeType()
                {
                    NodeTypeDescription = "abc",
                    Item = new ModelType() { ModelId = 123, ModelTitle = "123" },
                    Node = new NodeType[] {
                        new NodeType() { Item = "456", Node = null, NodeTypeDescription = "empty"},
                        new NodeType() { Item = "789", Node = null, NodeTypeDescription = "empty"},
                        new NodeType() { Item = "abc", Node = null, NodeTypeDescription = "empty"},
                    }
                };
            Dictionary<long, ModelType> nodes = root.Flaten(root);
           
        }
    }
    public class ModelType
    {
        public string ModelTitle;
        public long ModelId;
    }

    public class NodeType
    {
        public string NodeTypeDescription { get; set; }
        public object Item { get; set; }
        public NodeType[] Node { get; set; }

        public Dictionary<long, ModelType> Flaten(NodeType node)
        {
            Dictionary<long, ModelType> models = null;
            List<KeyValuePair<long, ModelType>> children = node.FlatenRecursive(node);

            if (node.GetType() == typeof(ModelType))
            {
                models = new Dictionary<long, ModelType>(); 

                models.Add(((ModelType)node.Item).ModelId, (ModelType)node.Item);
            }
            if (children != null)
            {
                foreach (KeyValuePair<long, ModelType> child in children)
                {
                    if (models == null) models = new Dictionary<long, ModelType>();
                    models.Add(child.Key, child.Value);
                }
            }
            return models;
        }
        public List<KeyValuePair<long,ModelType>> FlatenRecursive(NodeType node)
        {
            List<KeyValuePair<long, ModelType>> models = null;
            if(node.Item.GetType() == typeof(ModelType))
            {
                models = new List<KeyValuePair<long, ModelType>>();
                models.Add(new KeyValuePair<long,ModelType>(((ModelType)node.Item).ModelId, (ModelType)node.Item));
            }
            if (node.Node != null)
            {
                foreach (NodeType child in node.Node)
                {
                    List<KeyValuePair<long, ModelType>> children = child.FlatenRecursive(child);
                    if (children != null)
                    {
                        if (models == null) models = new List<KeyValuePair<long, ModelType>>();
                        models.AddRange(children);
                    }
                   
                }
            }
            return models;
        }
    }
    
}

Search Hierarchical Data Using Linq

2 Answers2