Optimized Hierarchy Traverser

My first draft of hierarchy traversing component got some serious feedback, and it's time to make some changes before moving on to the next challenges. Hierarchy traverser is not optimal yet as it uses tail-call recursion and it's easy to run to Stack Overflow with it. This blog post solves this problem and prepares for the next challenges like node cache and continue-from-given-node.

Problem: Running to Stack Overflow

As reader Ants pointed out then, .NET runtime doesn't always optimize tail-call recursion and using this simple piece of code, it's possible to run to Stack Overflow fast.

Let's define a hierarchy provider of the integer.

class IntHeirarchyProvider : 
IHierarchyProvider<int>{   
  public int MaxDepth { get; private set; }  
  public IntHeirarchyProvider(int maxDepth) => MaxDepth = maxDepth; 
  public bool HasRootNode => true;   
  public bool IsHierarchyNode(int node) => true;    
  public IList<int> LoadChildren(int node) => node < MaxDepth ? new List<int>() 
  { node + 1 } : null;    public int LoadRootNode

Now, let's run it using the following code going for a depth of 100K.

static void Main(string[] args){   
  var traverser = new HierarchyTraverser<int>(new IntHeirarchyProvider(100000)); 
  traverser.NodeLoaded += (s, e) => {
    if (e.Node % 1000 == 0) Console.WriteLine(e.Node); };   
  traverser.Start();}

Here's the resulting StackOverflowExcpetion:

Although, in practice, we don't meet document repositories or site menus with such depth. I want my solution to be ready also for other types of applications where such needs may raise.

Introducing Wrapper

I solved the problem by moving from recursion to stack. It solves the problem with Stack Overflow, but the price is a class that wraps hierarchy nodes. When using Stack, we cannot use anymore one simple list to keep the hierarchy path of the current node. We have to keep this information somewhere else, and the most logical choice for me was wrapper class.

public class NodeWrapper<T>{  
  public NodeWrapper<T> Parent { get; set; }  
  public T Node { get; set; }    public int Level { get; set; }}

Wrapper has some additional properties we need usually when migrating document repositories:

• Parent — when migrating to the document repository, then, very often in legacy systems, we have to know at least one or two parents of the current node. One example is forming a valid number for the document folder.
• Level — or current depth is sometimes used to recognize the type of document folder in the repository.

This little change actually affects other parts of the code, as we see in the next steps.

Better Hierarchy Provider

To make the code more logical, I also introduced — based on comments — root nodes collection. It means that there is no more need for checks if the hierarchy has one single root node or not.

public interface IHierarchyProvider<T>{   
  IList<T> LoadRootNodes();   
  IList<T> LoadChildren(T node);}

As wrapper nodes hold a reference to parent and level, I also changed the event arguments class to use the node wrapper.

public class NodeLoadedEventArgs<T>{  
  public NodeWrapper<T> Node { get; set; }}

Optimizing Hierarchy Traverser

Now, we have all changes done and it's time to write more effective hierarchy traverser. Instead of recursion, it uses Stack and a single loop to traverse through hierarchies. Here is the optimized version of previous hierarchy traverser.

public class HierarchyTraverser<T>{  
  public delegate void NodeLoadedEventHandler(object sender, NodeLoadedEventArgs<T> e);
  public event NodeLoadedEventHandler NodeLoaded;   
  private readonly IHierarchyProvider<T> _provider;    
  private bool _stop = false;    
  public HierarchyTraverser(IHierarchyProvider<T> provider)    {      
    _provider = provider;    }  
  public void Start()    {      
    var rootNodes = _provider.LoadRootNodes();    
    var stack = new Stack<NodeWrapper<T>>();    
    foreach (var rootNode in rootNodes)        {     
      stack.Push(new NodeWrapper<T> { Node = rootNode, Level = 0, Parent = null });        }         while (stack.Count > 0)        {            var node = stack.Pop();            OnLoadNode(node);             var children = _provider.LoadChildren(node.Node);            if (children == null)            {                continue;            }             foreach (var childNode in children)            {                if (_stop)                {                    break;                }                 stack.Push(new NodeWrapper<T>                           {                                Node = childNode,                                Level = node.Level + 1,                                Parent = node                           });            }        }    }     public void Stop()    {        _stop = true;    }     protected void OnLoadNode(NodeWrapper<T> node)    {        var args = new NodeLoadedEventArgs<T>        {            Node = node        };         NodeLoaded?.Invoke(this, args);    }}

Let's try out how these modifications work.

Hierarchy traverser can be written shorter using LINQ and lambdas but at this point I leave it like it is as. There's more code, yes, but it is not too cryptic for developers who are not familiar with hierarchies or who are new on the field. When I get to API layer, I will probably go here with shorter code.

Trying Out Modified Hierarchy Traverser

My main concern is Stack Overflow, of course. It should not happen with the new implementation, but still, let's try it out to be sure. As many things changed in the code, I had to update the integer hierarchy provider to reflect these changes.

class IntHeirarchyProvider : IHierarchyProvider<int>{   
  public int MaxDepth { get; private set; }  
  public IntHeirarchyProvider(int maxDepth) => MaxDepth = maxDepth; 
  public bool HasRootNode => true;    public bool IsHierarchyNode(int node) => true;   
  public IList<int> LoadChildren(int node) => node < MaxDepth ? new List<int>() {
    node + 1 } : null;    public IList<int> LoadRootNodes() => new List<int> { 1 };}

Test code needs small modifications before we can run it.

static void Main(string[] args){   
  var traverser = new HierarchyTraverser<int>(new IntHeirarchyProvider(100000)); 
  traverser.NodeLoaded += (s, e) => { 
    if (e.Node.Node % 1000 == 0) Console.WriteLine(e.Node.Level + 1); };  
  traverser.Start();}

Now, we don't run to Stack Overflow anymore.

Updated SharePoint Hierarchy Provider

Here is updated SharePoint hierarchy provider.

public class SPHierarchyProvider : IHierarchyProvider<SPFolder>, IDisposable{  
  private SPContentTypeId FolderContentTypeId = new SPContentTypeId("0x0120");   
  private SPSite _site;    private SPWeb _web;    private SPList _list;   
  public SPHierarchyProvider(string siteUrl, string webUrl, string listName)    {  
    _site = new SPSite(siteUrl);        _web = _site.OpenWeb(webUrl);       
    _list = _web.Lists[listName];    }   
  public IList<SPFolder> LoadChildren(SPFolder node)    {   
    return node.SubFolders.Cast<SPFolder>().ToList();    }   
  public IList<SPFolder> LoadRootNodes()    {     
    return new List<SPFolder> { _list.RootFolder };    }     
  #region IDisposable Support    private bool disposedValue = false;    
  protected virtual void Dispose(bool disposing)    {     
    if (!disposedValue)        {            if (disposing)          
    {                _web.Dispose();                _site.Dispose();      
    }             disposedValue = true;        }    }   
  public void Dispose()    {        Dispose(true);    } 
  #endregion}

For this provider, the parent node cache is mandatory, as the parent folder of SPFolder makes a round-trip to the database, and when exporting big document repositories, this one round-trip makes a huge difference.

Updated Database Hierarchy Provider

Also, hierarchy provider for simple SQL Server database needed updates after changes we made. An updated version of the provider can be found here.

public class DatabaseHierarchyProvider : IHierarchyProvider<DataRow>{  
  private readonly IDbConnection _connection;    
  public DatabaseHierarchyProvider(IDbConnection connection)    { 
    _connection = connection;    }     
  public IList<DataRow> LoadChildren(DataRow node)    {   
    using(var command = GetCommand(node))        {         
      var table = new DataTable();            
      table.Load(command.ExecuteReader());             
      return table.Rows.Cast<DataRow>().ToList();        
    }    }    
  private IDbCommand GetCommand(DataRow node)    {       
    if (node == null)        {          
      return GetRootItemsCommand();       
    }         
    return GetChildItemsCommand((int)node["Id"]);    
  }     private IDbCommand GetRootItemsCommand()    {       
    var sql = "SELECT * FROM Menu WHERE ParentId IS NULL";         
    var command = _connection.CreateCommand();        
    command.CommandText = sql;         return command;   
  }     private IDbCommand GetChildItemsCommand(int id)    {        
    var sql = "SELECT * FROM Menu WHERE ParentId = @Id";        
    var command = _connection.CreateCommand();        
    command.CommandText = sql;         
    var param = command.CreateParameter();        
    param.ParameterName = "@Id";        
    param.Value = id;         
    command.Parameters.Add(param);         
    return command;    }     
  public IList<DataRow> LoadRootNodes()    {        
    using (var command = GetCommand(null))        {           
      var table = new DataTable();            
      table.Load(command.ExecuteReader());             
      return table.Rows.Cast<DataRow>().ToList();       
    }    }}

Wrapping Up

Solving one simple problem may introduce many changes to the codebase, but if the architecture or technical design of the system gets better, then these changes are always justified. And, most important is to move towards bullet-proof code. This post introduced how to move from tail-recursion to stack and avoid a Stack Overflow Exception that was very easy to produce. The resulting components now have more power on working with hierarchies