Depth-First Hierarchy in C#
I was given a requirement recently where I needed to obtain a list of database records from a self-joining table, wherein each record would also provide the full hierarchy of that join, in reverse order.
To explain further, imagine a family tree described in a single table. Each record has its primary key of course, but would also have a “ParentID” field to describe the hierarchy. The top-most parent could contain “null” and each child would store the primary key of another parent record in the table, in the “ParentID” field. Now imagine looping through these records and building a new string for each, which would contain the hierarchy, from the bottom-up.
Recursion might be the first thing that pops into your head, and you’d be right! Typically you’d use recursion in the opposite direction (top-down) for normal tasks, which can make this particular problem confusing, at first. A good algorithmic pattern for “bottom-up”, and the one I’m going to show you, is called “Depth-First”.
Here’s a quick tutorial on using the depth-first approach to obtaining hierarchical data, in reverse, in C#.
We’re going to fake the family tree data described earlier in a simple List collection, within a simple C# Console Application.
First, let’s model our mock data in a single class, called Item.
public class Item {
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public string Path { get; set; }public Item(int id, int parentId, string name) {
Id = id;
ParentId = parentId;
Name = name;
}
}
We have our “self-joining” primary and foreign-keys with Id and ParentId. The name describes the Item being created, and the Path will be used to hold the reverse-order of each Item’s full depth-first hierarchy, as each item is analyzed to determine it.
This will all make better sense, shortly.
Carrying on, let’s create our data from this entity class, in the program’s Main method.
static void Main(string[] args) {
var items = new List<Item>() {
new Item(1, 0, “Ralph”),
new Item(2, 1, “Ron”),
new Item(3, 2, “Vin”),
new Item(4, 3, “Armando”),
new Item(5, 3, “Alex”),
new Item(6, 3, “Ana”)
};
}This is my family tree, starting with my grandfather Ralph, all the way down to my youngest child, Ana. I’ve used a zero in the ParentId property/param to define the top-most record in the hierarchy — on that has no parent.
Now, how do we pull this off? What kind of sadistic looking, mad scientist logic must be concocted to fulfill this insane requirement? It’s surprisingly easy, thanks to C# Delegates and Lambda syntax. In a terse, 15-line method of expressive code, this can be achieved.
static string GetParentsString(List<Item> all, Item current) {
string path = “”;
Action<List<Item>, Item> GetPath = null;
GetPath = (List<Item> ps, Item p) => {
var parents = all.Where(x => x.Id == p.ParentId);
foreach (var parent in parents) {
path += $”/{parent.Name}”;
GetPath(ps, parent);
}
};
GetPath(all, current);
string[] split = path.Split(new char[] { ‘/’ });
Array.Reverse(split);
return string.Join(“/”, split);
}This may look a little strange at first, but allow me to break it down line-by-line. First, I’ve declared the full depth-first hierarchy string value I’m going to build. Next, I’m declaring an Action delegate, which I define on the following line. Essentially, this is a function which takes a full list of Item objects and a single Item, as parameters. This way, I can describe a method to fire at a later time, which will build the value of the path variable. In fact, this happens on the line immediately after.
Why?
This is called a “closure”, or a function within a function, which has access to the surrounding scope. In this case, I can call GetPath inside of this GetParentsString method, obtain my path value, and return it in a thread-safe manner. I’m not writing to a global variable which may not be safe in the context of which I’m using this code. Basically, it’s a self-containing mechanism in which you can pass in all of your items, and your “current item” in a loop, and get a path string of the full hierarchy I’ve been discussing.
The GetPath delegate itself, is a little more confusing. It inspects the entire list of Item entities for a any that match the current Item’s parent. In plain English, “Give me all of the parents of this item”. It then loops through the results in the parents list and writes to the path value. You may have noticed that it calls itself afterward, inside of the loop. This is where we use recursion to traverse upward through the hierarchy, until we run out of parent node Items. Passing in the same list of all Item objects, as well as the current parent in the loop, it inspects itself and writes to the path string value, until no parents remain in the list.
The last few lines of GetParentsString deal with reversing the order of our results and formatting them for presentation.
The quick, functional way to loop through these records to see the results, would be this single line of code. Place this below the list of Item entities we defined in the very beginning.
items.ForEach(item => Console.WriteLine($”({item.Id}): {item.Name} {GetParentsString(items, item)}”));Phew! That’s a lot to digest in a small chunk of code. To understand it better, I invite you to try it yourself. Here’s the entire class, and indeed the entire project, in one file.
using System;
using System.Collections.Generic;
using System.Linq;namespace DepthFirstTreeTraversal {
public class Item {
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public string Path { get; set; } public Item(int id, int parentId, string name) {
Id = id;
ParentId = parentId;
Name = name;
}
} class Program {
static void Main(string[] args) {
var items = new List<Item>() {
new Item(1, 0, “Ralph”),
new Item(2, 1, “Ron”),
new Item(3, 2, “Vin”),
new Item(4, 3, “Armando”),
new Item(5, 3, “Alex”),
new Item(6, 3, “Ana”)
};
items.ForEach(item => Console.WriteLine($”({item.Id}): {item.Name} {GetParentsString(items, item)}”));
Console.ReadLine();
} static string GetParentsString(List<Item> all, Item current) {
string path = “”;
Action<List<Item>, Item> GetPath = null;
GetPath = (List<Item> ps, Item p) => {
var parents = all.Where(x => x.Id == p.ParentId);
foreach (var parent in parents) {
path += $”/{parent.Name}”;
GetPath(ps, parent);
}
};
GetPath(all, current);
string[] split = path.Split(new char[] { ‘/’ });
Array.Reverse(split);
return string.Join(“/”, split);
}
}
}
Apologies for the formatting, I know it’s heinous. Hopefully you pasted this into Visual Studio and it looks fabulous. Someday, I’ll take a minute to figure out how to use a Gist, and will start posting readable samples.
Enjoy!
