using System.Collections.Generic;
public class HierarchicalNode<T> where T : IComparable
public HierarchicalNode<T> Parent {get;}
public List<HierarchicalNode<T>> Children {get;}
public HierarchicalNode(T value, HierarchicalNode<T> parent = null)
this.Children = new List<HierarchicalNode<T>>();
parent?.Children.Add(this);
public bool IsAncestorOf(HierarchicalNode<T> item, bool includeSelf = true)
includeSelf && this.Value.CompareTo(item.Value) == 0
|| IsAncestorOf(item.Parent)
public bool IsDescendantOf(HierarchicalNode<T> item, bool includeSelf = true)
includeSelf && this.Value.CompareTo(item.Value) == 0
|| (this.Parent?.IsDescendantOf(item) ?? false)
return this.Parent == null;
public IEnumerable<T> GetDescendants(bool includeSelf = false)
foreach (var child in Children)
yield return child.Value;
foreach (var descendant in child.GetDescendants())
public IEnumerable<T> GetAncestors(bool includeSelf = false)
foreach (var ancestor in this?.Parent?.GetAncestors(true) ?? Enumerable.Empty<T>())
public class HierarchicalDictionary<Key, T>
private Dictionary<Key, HierarchicalNode<T>> dict = new Dictionary<Key, HierarchicalNode<T>>();
private Func<T, Key> getKey;
Func<T, Key> getParentKey;
public HierarchicalDictionary(Func<T, Key> getKey, Func<T, Key> getParentKey)
this.getParentKey = getParentKey;
public void Add(T item) {
if (item == null) throw new ArgumentNullException(nameof(item));
var parentKey = getParentKey(item);
if (parentKey != null && !dict.Keys.Contains(parentKey)) {
throw new InvalidOperationException($"Parent must exist before child can be added. Key [{key}]. ParentKey [{parentKey}]");
if (dict.Keys.Contains(key)) {
throw new InvalidOperationException($"An object with the key [{key}] already exists");
var parent = parentKey == null ? null : dict[parentKey];
var node = new HierarchicalNode<T>(item, parent);
public void AddRange(IEnumerable<T> item)
public bool IsAncestorOfByKey(Key a, Key b, bool includeSelf = true)
return objA.IsAncestorOf(objB);
public bool IsDescendantOfByKey(Key a, Key b, bool includeSelf = true)
return objA.IsDescendantOf(objB);
public IEnumerable<T> GetDescendantsOfByKey(Key key)
return dict[key].GetDescendants();
public IEnumerable<T> GetAncestorsOfByKey(Key key)
return dict[key].GetAncestors();
public class Employee: IComparable
public string Name {get;}
public string ManagerId {get;}
public Employee (string id, string name, string managerId)
public int CompareTo(object obj) {
return this.Id.CompareTo((obj as Employee)?.Id);
public static void Main()
var employees = new Employee[]
new ("bigcheese@example.com","Brie Emmental", null),
new ("assistant@example.com","Adrian Steward","bigcheese@example.com"),
new ("manager@example.com","Max Power", "bigcheese@example.com"),
new ("junior@example.com","Robert Ott","manager@example.com"),
new ("subordinate@example.com","Anne Droid","manager@example.com"),
new ("lackey@example.com","Simon Borg","subordinate@example.com"),
new ("personA@different.example.com","Person A",null),
new ("personB@different.example.com","Person B","personA@different.example.com"),
new ("personC@different.example.com","Person C","personB@different.example.com"),
new ("personX@different.example.com","Person X","personC@different.example.com"),
new ("personY@different.example.com","Person Y","personC@different.example.com"),
new ("personZ@different.example.com","Person Z","personC@different.example.com")
var roster = new HierarchicalDictionary<string, Employee>(x => x.Id, x => x.ManagerId);
roster.AddRange(employees);
foreach (var a in employees)
foreach (var b in employees)
var relationship = roster.IsAncestorOfByKey(a.Id, b.Id) ? "manages" : "does not manage";
Console.WriteLine($"[{a.Name}] {relationship} [{b.Name}]");
relationship = roster.IsDescendantOfByKey(a.Id, b.Id) ? "reports to" : "does not report to";
Console.WriteLine($"[{a.Name}] {relationship} [{b.Name}]");
foreach (var descendant in roster.GetDescendantsOfByKey("manager@example.com"))
Console.WriteLine($"Employees Of Max: [{descendant.Name}]");
foreach (var descendant in roster.GetAncestorsOfByKey("junior@example.com"))
Console.WriteLine($"Managers Of Robert: [{descendant.Name}]");
Console.WriteLine("End of demo");