Converting table in tree

Question

Is there any scope for improvement in my program which converts flat db entity to a tree data structure. I don't want to loose the Generic flexibility as i should be able to use the same method for any other DBEntity class

Interface for db entity class

public interface IDbEntityNode
    {
         int Id { get; set; }
         int ParentId { get; set; }
    }

Example of db Entity class

 public class ExceptionCategory :IDbEntityNode
    {
        public  int Id { get; set; }
        public  int ParentId { get; set; }
        public string Data { get; set; }      
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }

Generic class which holds the structure of tree node

public class GenericNode<T> 
    {
        public T NodeInformation { get; set; }
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; } = new List<GenericNode<T>>();
    }

Method which coverts flat list to tree

public static List<GenericNode<T>> CreateGenericTree<T>(List<T> flatDataObject,Func<T,bool> IsRootNode) where T : IDbEntityNode            
        {
            var lookup = new Dictionary<int, GenericNode<T>>();
            var rootNodes = new List<GenericNode<T>>();
            var noOfElements = flatDataObject.Count;
            for (int element = 0; element < noOfElements; element++)
            {
                GenericNode<T> currentNode;
                if (lookup.TryGetValue(flatDataObject[element].Id, out currentNode))
                {
                    currentNode.NodeInformation = flatDataObject[element];
                }
                else
                {
                    currentNode = new GenericNode<T>() { NodeInformation = flatDataObject[element] };
                    lookup.Add(flatDataObject[element].Id, currentNode);
                }

                if (IsRootNode(flatDataObject[element])) 
                {
                    rootNodes.Add(currentNode);
                }
                else
                {
                    GenericNode<T> parentNode;
                    if (!lookup.TryGetValue(flatDataObject[element].ParentId, out parentNode))
                    {   
                        parentNode = new GenericNode<T>();
                        lookup.Add(flatDataObject[element].ParentId, parentNode);
                    }
                    parentNode.Children.Add(currentNode);
                    currentNode.Parent = parentNode;
                }
            }

            return rootNodes;
        }

Execution:

private static void Main(string[] args)
        {
            List<IDbEntityNode> flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            var tree = CreateGenericTree(flatDataStructure, IsRootNode);
        }
 private static bool IsRootNode(IDbEntityNode dbEntity)
        {
            bool isRootNode = false;
            if (dbEntity.ParentId == 0 )
                isRootNode = true;
            return isRootNode;              
        }

I am confused why u use generic. I would have a list of node object which has a list of node objects. This presents a real tree.. — Aldert, Sep 15 '18 at 14:31
@Aldert table is kind of data base entity and initial goal was to create one method where i can convert any entity with same properties to tree...I will take your suggestion and try to improve the code — A.Learn, Sep 15 '18 at 16:41
@jdweng Please check out the question again...I did made improvements in my program according to your comments...let me know if there is any scope for improvements — A.Learn, Sep 19 '18 at 18:40
You code is only a single layer an not a tree. Take a look at my solution at following posting : https://stackoverflow.com/questions/52279476/recursive-linq-get-hierarchy/52280500#comment91511563_52280500 — jdweng, Sep 19 '18 at 19:46
@jdweng could you please explain why its a single layer and not a tree — A.Learn, Sep 19 '18 at 19:56
When you run your code how many descendant layer does GenericNode contain? It looks like your sample input has many case where there are 3 layers like 0->12->14. I would add some more complicated case with more layer just to make sure your code is working correctly. The link I provided does correctly create the tree. — jdweng, Sep 19 '18 at 23:48
@jdweng This is not the real dbEntity. I just made it, so user can focus on tree algo rather than complex dbEntity. I tested my code with real dBEntity and it works fine. Thanks anyway for raising the concern — A.Learn, Sep 20 '18 at 03:45

score 0 · Accepted Answer · answered Sep 16 '18 at 17:14

Created a generic approach, table objects need to follow the dbSet interface and TreeNode objects need to follow the ITreeNode. I used binarySerach to make this as fast as possible. No recursion needed. The logic ensures that you do not need to have the items in a particular order. I did not throw an error when out of the loop when there are still unassigned objects, this can be easy added.

    using System.Collections.Generic;

public interface ITreeNode
{
    string ParentId { get; set; }
    string Id { get; set; }
    dbItem item { get; set; }
    List<ITreeNode> Nodes { get; set; }
}

public class TreeNode : ITreeNode
{
    public TreeNode()
    { }

    public string ParentId { get; set; }
    public string Id { get; set; }
    public dbItem item { get; set; }
    public List<ITreeNode> Nodes { get; set; }
}

public class dbItem
{
    public string ParentId { get; set; }
    public string Id { get; set; }
    public string Name { get; set; }
}
class app
{


    static void Main()
    {
        List<dbItem> dbSet = new List<dbItem>();

        dbSet.Add(new dbItem() { Id = "5", ParentId = "1", Name = "Jan" });
        dbSet.Add(new dbItem() { Id = "25", ParentId = "1", Name = "Maria" });
        dbSet.Add(new dbItem() { Id = "1", Name = "John" });
        dbSet.Add(new dbItem() { Id = "8", ParentId = "2", Name = "Cornelis" });
        dbSet.Add(new dbItem() { Id = "2", Name = "Ilse" });
        dbSet.Add(new dbItem() { Id = "3", Name = "Nick" });
        dbSet.Add(new dbItem() { Id = "87", ParentId = "5", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "67", ParentId = "3000", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "3000", Name = "Max" });

        List<TreeNode> result = BuildTree<TreeNode>(dbSet);

    }

    private class ParentComparer<T> : IComparer<ITreeNode> where T: ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
            if (x.ParentId == null) return -1; //have the parents first
            return x.ParentId.CompareTo(y.ParentId);
        }
    }
    private class IdComparer<T> : IComparer<ITreeNode> where T : ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
           return x.Id.CompareTo(y.Id);
        }
    }

    static private List<T> BuildTree<T> (List<dbItem> table) where T: ITreeNode, new()
    {
        //temporary list of tree nodes to build the tree
        List<T> tmpNotAssignedNodes = new List<T>();
        List<T> tmpIdNodes = new List<T>();
        List<T> roots = new List<T>();

        IComparer<T> pc = (IComparer<T>) new ParentComparer<T>();
        IComparer<T> ic = (IComparer<T>) new IdComparer<T>();

        foreach (dbItem item in table)
        {
            T newNode = new T() { Id = item.Id, ParentId = item.ParentId, item = item };
            newNode.Nodes = new List<ITreeNode>();
            T dummySearchNode = new T() { Id = item.ParentId, ParentId = item.ParentId };

            if (string.IsNullOrEmpty(item.ParentId))
                roots.Add(newNode);
            else
            {
                int parentIndex = tmpIdNodes.BinarySearch(dummySearchNode, ic);//Get the parent
                if (parentIndex >=0)
                {
                    T parent = tmpIdNodes[parentIndex];
                    parent.Nodes.Add(newNode);
                }
                else
                {
                    parentIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);
                    if (parentIndex < 0) parentIndex = ~parentIndex;
                    tmpNotAssignedNodes.Insert(parentIndex, newNode);
                }
            }

            dummySearchNode.ParentId = newNode.Id;

            //Cleanup Unassigned
            int unAssignedChildIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);

            while (unAssignedChildIndex >= 0 && unAssignedChildIndex < tmpNotAssignedNodes.Count)
            {
                if (dummySearchNode.ParentId == tmpNotAssignedNodes[unAssignedChildIndex].ParentId)
                {
                    T child = tmpNotAssignedNodes[unAssignedChildIndex];
                    newNode.Nodes.Add(child);
                    tmpNotAssignedNodes.RemoveAt(unAssignedChildIndex);
                }
                else unAssignedChildIndex--;
            }
            int index = tmpIdNodes.BinarySearch(newNode, ic);
            tmpIdNodes.Insert(~index, newNode);

        }


        return roots;
    }
}

I also created my own implementation after looking at comments but that did not had Generic implementation...Yours do!!! — A.Learn, Sep 17 '18 at 18:01
I removed it from answer as it is not Generic and can only work with dbEntity where improved program in question can work with any entity implementing interface and also has o(n) time complexity — A.Learn, Sep 19 '18 at 18:58
ok...I guess I should still mark your solution as answer as I got inspiration to write my own method from there...but do let me know if I can improve my program — A.Learn, Sep 19 '18 at 19:08

jdweng · Answer 2 · 2018-09-20T10:19:28.740

Try following solution using recursive code :

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

namespace ConsoleApplication1
{
    class Program
    {
        public static List<IDbEntityNode> flatDataStructure = null;
        public static Dictionary<int?, List<IDbEntityNode>> dict = null;
        static void Main(string[] args)
        {
            flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            dict = flatDataStructure.GroupBy(x => x.ParentId, y => y)
                .ToDictionary(x => x.Key, y => y.ToList());

            GenericNode<IDbEntityNode> root = new GenericNode<IDbEntityNode>();
            root.Parent = null;
            int rootId = 0;
            root.NodeInformation.Id = rootId;
            root.NodeInformation.name = "root";
            root.NodeInformation.ParentId = null;
            CreateGenericTree(root);
        }
        public static void CreateGenericTree<T>(GenericNode<T> parent) where T : IDbEntityNode, new()
        {
            if (dict.ContainsKey(parent.NodeInformation.Id))
            {
                List<IDbEntityNode> children = dict[parent.NodeInformation.Id];
                foreach (IDbEntityNode child in children)
                {
                    GenericNode<T> newChild = new GenericNode<T>();
                    if (parent.Children == null) parent.Children = new List<GenericNode<T>>();
                    parent.Children.Add(newChild);
                    newChild.NodeInformation.Id = child.Id;
                    newChild.NodeInformation.ParentId = parent.NodeInformation.Id;
                    newChild.NodeInformation.name = child.name;
                    newChild.Parent = parent;

                    CreateGenericTree(newChild);
                }
            }
        }

    }
    public class GenericNode<T> where T : new()
    {
        public T NodeInformation = new T();
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; }
    }
    public class IDbEntityNode
    {
        public int Id { get; set; }
        public int? ParentId { get; set; }
        public string name { get; set; }
    }
    public class ExceptionCategory : IDbEntityNode
    {
        public string Data { get; set; }
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }
}

When i created the tree about a million times your code is about 500% slower that code mentioned in question. You can test it by yourself — A.Learn, Sep 20 '18 at 05:44
There are two methods for creating trees 1) Push-Pop method (Aldert solution) 2) Recursive. I'm searching through source data a lot of times. Will create a dictionary to speed things up — jdweng, Sep 20 '18 at 10:06

Converting table in tree

2 Answers2

Linked