Converting Nested Set Data to Tree Object

In a project at work we decided to use the nested set model. It fit very well with our needs. We set up the database schema and also created some procedures to help with inserting and deleting nodes. The next step is now reading the data from a client.  However we want to read the data and make sure the objects are represented in a tree structure.  So how do we take tabular data and convert it into a tree?  Easy, recursion.  We can sort the data by the left value, which should give us the ability to step through using a depth-first approach.

I'm not going to go into what the nested set model is, I'm assuming that since you are here you know something about it.  If not then I recommend the de facto blog here: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Data Structures

First step is we need to define a data structure for our nodes.  It will contain the id, name, and list of child nodes.  You'll notice I set the properties for left and right to internal.  This is because there is no value giving users access to these properties so they should only be accessible within the project.

public class Node
{
 private double category_id = 0;
 private string name = "";
 private int left;
 private int right;
 private List<Node> nodes = new List<Node>();

 public Node()
 {
 }

 public Node(double category_id, string name, int left, int right)
 {
  this.CategoryId = category_id;
  this.Name = name;
  this.Left = left;
  this.Right = right;
 }

 public double CategoryId
 {
  get { return category_id; }
  set { category_id = value; }
 }

 public string Name
 {
  get { return name; }
  set { name = value; }
 }

 internal int Left
 {
  get { return left; }
  set { left = value; }
 }

 internal int Right
 {
  get { return right; }
  set { right = value; }
 }

 public List<Node> Nodes
 {
  get { return nodes; }
  set { nodes = value; }
 }
}

Okay this looks good.

Public Method

Next we can create the public method to open a connection to the database, load the data into a list, then pass that list off to a recursive function called "BuildNodes()" that will generate the node hierarchy, which we will then return.  Notice we are sorting the results the by left value in the SQL command.

public Node GetNodes()
{
 Node root = null;

 try
 {
  List<Node> nodes = new List<Node>();

  // connection 
  using (MySqlConnection connection = new MySqlConnection(_connectionstring))
  {
   //Open connection
   connection.Open();

   //Create command
   using (MySqlCommand command = new MySqlCommand("SELECT * FROM nested_category ORDER BY lft", connection))
   {
    //Read the table row
    using (MySqlDataReader reader = command.ExecuteReader())
    {
     //Read row values
     Node node;
     while (reader.Read())
     {
      node = new Node(); 
      node.CategoryId = Convert.ToDouble(reader["id"]);
      node.Text = reader["text"];
      node.Left = Convert.ToInt(reader["lft"]);
      node.Right = Convert.ToInt(reader["rgt"]);

      nodes.Add(node);
     }
    }
   }
  }

  if (nodes.Count == 0)
   return null;

  //Build the node hierarchy
  int nodeIndex = 0;
  root = BuildNodes(nodes, ref nodeIndex);
 }
 catch (Exception ex)
 {
  throw new Exception(ex);
 }

 return root;
}

Recursive Method

The last step is the recursive method to step through the list and convert it to a tree structure.  The trick here is to track 3 values, the row index and then the left and right values of the node in that row index.  The flow is hierarchy

1. If a leaf node (a node without children) then return the node.
2. If an internal node (a node with children) then
1. Continue to step through the list and add children while the child's right value is less than the node's right value.

private Node BuildNodes(List<Node> nodes, ref int nodeIndex)
{
 
 Node node = nodes[nodeIndex];
 if ((node.Right - node.Left) == 1)
 {
  //Leaf
  return node;
 }
 else
 {
  //Internal node     
  Node child;
  int childIndex = node.Left++;
  while (childIndex + 1 < node.Right)
  {
   nodeIndex++;
   child = BuildNodes(nodes, ref nodeIndex);
   if (child != null)
   {
    childIndex = child.Right++;
    node.Nodes.Add(child);
   }
  }    
 }

 return node;
}

This will build up the hierarchy converted from a list.  It assumes that the left and right values are continuous and there are no numbers missing.  If your list filters the tree and there are gaps in the left and right values then good luck and let me know what you find.