Recursive method turning flat structure to recursive

Question

I often end up working with systems where the data is delivered with some Id property and possibly a parentId prop, but never do anyone tempt to actually give me a nice recursive object to play with.

Now, the code below is merely a suggestion in how to solve these kind of "problems", I've created the FlatObject to simulate an incoming with data.

class Program
{
 static void Main(string[] args)
 {
 // Fill list with sample data
 List<FlatObject> flatObjects = new List<FlatObject>
 {
 new FlatObject(1,0),
 new FlatObject(2,0),
 new FlatObject(3,0),
 new FlatObject(4,0),
 new FlatObject(5,1),
 new FlatObject(6,2),
 new FlatObject(7,6),
 new FlatObject(8,6)
 };
 // call the recursive method
 var recursiveObjects = FillRecursive(flatObjects, 0);
 }
 private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
 {
 List<RecursiveObject> recursiveObjects = new List<RecursiveObject>();
 foreach (var item in flatObjects.Where(x => x.ParentId.Equals(parentId)))
 {
 recursiveObjects.Add(new RecursiveObject
 {
 Id = item.Id,
 ParentId = item.ParentId,
 Children = FillRecursive(flatObjects, item.Id)
 });
 }
 return recursiveObjects;
 }
}
public class FlatObject
{
 public int Id { get; set; }
 public int ParentId { get; set; }
 public FlatObject(int id, int parentId)
 {
 Id = id;
 ParentId = parentId;
 }
}
public class RecursiveObject
{
 public int Id { get; set; }
 public int ParentId { get; set; }
 public List<RecursiveObject> Children { get; set; }
}

I am aware of some Linq alternatives to solve the foreach loop but that does hardly not change the approach of this.

private static List<RecursiveObject> FillRecursive(List<FlatObject> flatObjects, int parentId)
{
 return flatObjects.Where(x => x.ParentId.Equals(parentId)).Select(item => new RecursiveObject
 {
 Id = item.Id, ParentId = item.ParentId, Children = FillRecursive(flatObjects, item.Id)
 }).ToList();
}

• Mike Nakis: Looks beautiful. I would have used the term 'hierarchical' rather than 'recursive' in many places, however. Including the title.
• Dr. Wily's Apprentice: Don't mean to nit-pick, but just trying to point out some potential issues. This approach works when your data has a single root (ParentId: 0). If your data happens to have multiple distinct roots (a disconnected graph), though, then I think you'll miss some of the data. It looks like circular references would probably cause infinite recursion (stack overflow exception).

Answer 1

Below is the code for my approach. A benefit is that the heirarchy goes both ways; up and down. While the parent object contains a list of child objects, each child has a reference to the parent object.

Some differences from your original setup:

• The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
• The Children property on RecursiveObject is IEnumerable instead of List. This prevents consumers from modifying the contents of the list. If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
• I've made the Id, Parent, and Children properties on RecursiveObject read-only. This certainly isn't necessary, but you can do that if desired. This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.

The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id. Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.

class FlatObject
{
 public int Id { get; set; }
 public int? ParentId { get; set; }
}
class RecursiveObject
{
 public int Id { get; private set; }
 public RecursiveObject Parent { get; private set; }
 public IEnumerable<RecursiveObject> Children { get; private set; }
 public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
 {
 // convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
 var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject { Id = item.Id }).ToDictionary(item => item.Id);
 // group flat objects by their ParentId
 var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
 foreach (var group in flatObjectsGroupedByParentId)
 {
 // find each group's parent object
 RecursiveObject parent;
 if (recursiveObjectsById.TryGetValue(group.Key, out parent))
 {
 // convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
 parent.Children = group.Select(item => recursiveObjectsById[item.Id]).ToList();
 // assign the parent object to each child object
 foreach (var child in parent.Children)
 {
 child.Parent = parent;
 }
 }
 else
 {
 // something's wrong!!! ParentId refers to a non-existant object.
 }
 }
 return recursiveObjectsById.Values;
 }
}

EDIT: Added an "improved" version of my original approach, shown below. The following implementation provides the following benefits:

• The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization. The Children property getter checks if the _Children field is null, and if so it returns the default instance of the EmptyEnumerable<RecursiveObject> class (code included).
• Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
• The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
• The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.

• My setup code includes a second root (new FlatObject(9,-1)) and circular references (new FlatObject(10,10) and new FlatObject(0,2)), just to verify that the implementation can handle these special cases.

  class FlatObject
  {
   public int Id { get; set; }
   public int? ParentId { get; set; }
   public FlatObject(int id)
   {
   this.Id = id;
   }
   public FlatObject(int id, int parentId)
   : this(id)
   {
   this.ParentId = parentId;
   }
  }
  class RecursiveObject
  {
   public int Id { get; private set; }
   public RecursiveObject Parent { get; private set; }
   private List<RecursiveObject> _Children;
   public IEnumerable<RecursiveObject> Children
   {
   get
   {
   IEnumerable<RecursiveObject> value = _Children;
   if (value == null)
   value = EmptyEnumerable<RecursiveObject>.Default;
   return value;
   }
   }
   public RecursiveObject(int id)
   {
   this.Id = id;
   }
   public void AddChild(RecursiveObject child)
   {
   if (_Children == null)
   _Children = new List<RecursiveObject>();
   _Children.Add(child);
   child.Parent = this;
   }
   public bool RemoveChild(RecursiveObject child)
   {
   if (_Children != null)
   {
   bool removed = _Children.Remove(child);
   if (removed)
   child.Parent = null;
   return removed;
   }
   else
   {
   return false;
   }
   }
   public void AddChildren(IEnumerable<RecursiveObject> children)
   {
   if (children == null)
   throw new ArgumentNullException("children");
   if (_Children == null)
   _Children = new List<RecursiveObject>(children);
   else
   _Children.AddRange(children);
   foreach (var child in children)
   {
   child.Parent = this;
   }
   }
  }
  class Program
  {
   public static IEnumerable<RecursiveObject> FlatObjectsToRecursiveObjects(IEnumerable<FlatObject> flatObjects)
   {
   // convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
   var recursiveObjectsById = flatObjects.Select(item => new RecursiveObject(item.Id)).ToDictionary(item => item.Id);
   // group flat objects by their ParentId
   var flatObjectsGroupedByParentId = flatObjects.Where(item => item.ParentId.HasValue).GroupBy(item => item.ParentId.Value);
   foreach (var group in flatObjectsGroupedByParentId)
   {
   // find each group's parent object
   RecursiveObject parent;
   if (recursiveObjectsById.TryGetValue(group.Key, out parent))
   {
   // convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
   parent.AddChildren(group.Select(item => recursiveObjectsById[item.Id]));
   }
   else
   {
   // something's wrong!!! ParentId refers to a non-existant object.
   }
   }
   return recursiveObjectsById.Values;
   }
   static void Main(string[] args)
   {
   List<FlatObject> flatObjects = new List<FlatObject>()
   {
   new FlatObject(1,0),
   new FlatObject(2,0),
   new FlatObject(3,0),
   new FlatObject(4,0),
   new FlatObject(5,1),
   new FlatObject(6,2),
   new FlatObject(7,6),
   new FlatObject(8,6),
   new FlatObject(9,-1),
   new FlatObject(10,10),
   new FlatObject(0,2),
   };
   var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
   }
  }
  #region Universal Code
  class EmptyEnumerator<T> : IEnumerator<T>
  {
   public static readonly EmptyEnumerator<T> Default = new EmptyEnumerator<T>();
   public T Current
   {
   get { throw new InvalidOperationException(); }
   }
   public void Dispose()
   {
   }
   object System.Collections.IEnumerator.Current
   {
   get { throw new InvalidOperationException(); }
   }
   public bool MoveNext()
   {
   return false;
   }
   public void Reset()
   {
   }
  }
  class EmptyEnumerable<T> : IEnumerable<T>
  {
   public static readonly EmptyEnumerable<T> Default = new EmptyEnumerable<T>();
   public IEnumerator<T> GetEnumerator()
   {
   return EmptyEnumerator<T>.Default;
   }
   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
   {
   return this.GetEnumerator();
   }
  }
  #endregion
  

Answer 2

You could, perhaps, derive RecursiveObject from FlatObject.

In the degenerate case in which all objects belong to a single lineage (every object has one and only one child, except the last one) and you have lots of objects, then your recursive method will try to use an awful lot of stack space, possibly failing with a stack overflow exception. The way to correct this is by avoiding recursion and adding a stack data structure within your function, which then works in a loop. But of course you would not want to do that unless there is a very clear possibility of such a degenerate case ever occurring.

Answer 3

I'm a fan of immutable objects and collection initializer syntax, myself:

 private static void Main()
 {
 // Fill list with sample data
 FlatObjectList flatObjects = new FlatObjectList
 {
 { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 0 }, { 5, 1 }, { 6, 2 }, { 7, 6 }, { 8, 6 }
 };
 // call the recursive method
 RecursiveObjectList recursiveObjects = FillRecursive(flatObjects, 0);
 }
 private static RecursiveObjectList FillRecursive(IEnumerable<FlatObject> flatObjects, int parentId)
 {
 return new RecursiveObjectList(flatObjects
 .Where(x => x.ParentId.Equals(parentId))
 .Select(item => new RecursiveObject(item.Id, item.ParentId, FillRecursive(flatObjects, item.Id))));
 }
}
public sealed class FlatObjectList : List<FlatObject>
{
 public void Add(int id, int parentId)
 {
 this.Add(new FlatObject(id, parentId));
 }
}
public sealed class RecursiveObjectList : List<RecursiveObject>
{
 public RecursiveObjectList(IEnumerable<RecursiveObject> list)
 {
 this.AddRange(list);
 }
 public void Add(int id, int parentId, RecursiveObjectList children)
 {
 this.Add(new RecursiveObject(id, parentId, children));
 }
}
public sealed class FlatObject
{
 private readonly int id;
 private readonly int parentId;
 public int Id { get { return this.id; } }
 public int ParentId { get { return this.parentId; } }
 public FlatObject(int id, int parentId)
 {
 this.id = id;
 this.parentId = parentId;
 }
}
public sealed class RecursiveObject
{
 private readonly int id;
 private readonly int parentId;
 private readonly ReadOnlyCollection<RecursiveObject> children;
 public RecursiveObject(int id, int parentId, IList<RecursiveObject> children)
 {
 this.id = id;
 this.parentId = parentId;
 this.children = new ReadOnlyCollection<RecursiveObject>(children);
 }
 public int Id { get { return this.id; } }
 public int ParentId { get { return this.parentId; } }
 public ReadOnlyCollection<RecursiveObject> Children { get { return this.children; } }
}

• Mike Nakis: I am also a big fan of immutable objects and readonly members, but what is the point in adding accessor properties for readonly members?
• Jesse C. Slicer: So anyone who uses those objects can read them, yes?
• Mike Nakis: Sorry, my mistake, I did not word the question properly. Let me put it another way: Given that the members are readonly, why make them private? Make them public and you do not have to provide accessor properties for them! The "All thy members shall be private" clause sounds like a religious doctrine to me, superstitiously followed by people for no good reason: if it is readonly, it does not have to be private!
• Jesse C. Slicer: The best practice is to have all external access be through property accessors in the case the internals of your object need to change in the future. In one example, I can change the internal type of id to a string, but as long as the accessor can convert it to an int, the contract is intact. If I expose the field directly, I a) don't have that luxury and b) cannot ensure binary compatibility any more with my callers without a recompile.
• Mike Nakis: I see, the question has already been Skeeted.