Hydrate the tree off the table

Question

I have a DataTable with all my nodes. They were serialized into a database. I want to create a graphical representation of (hierarchical) data objects. There seem to be several methods for this.

This article describes a high-order method (this means that it requires a large DataTable search before the tree is fully built)

Is there an Order-N approach? In my case, I pre-sorted the tree nodes in a DataTable on the order form. Value, the first line shows NULL for the parent, because it is the root. Each subsequent line is sorted as a sequence .

I seem to recall the Order-N approach from my school days. But I do not remember.

My DataTable's schema looks like this:

• NodeID - int
• ParentNodeId - nullable
• Data row

Answer 1

Here is an algorithm that should do what you need. It assumes your data is ok, so it runs in O (n).

First you need a node that looks like this:

class Node { Node Parent; List<Node> Children = new List<Node>(); int NodeId; string Data; public Node(NodeRow row) { ... } } 

• Download the first line as current .
• Download the following line; compare newRow.ParentNodeId with current.NodeId .
• Until you find a match, set current = current.Parent
• Add newRow to current.Children and set current to a new line.
• Go to step 2.

What is it! If your data is properly structured, you do not need to do any additional null checks.

Example:

 Node CreateTree(IEnumerable<NodeRow> rows) { Node root = null; Node current = null; foreach (var row in rows) { // Root: if (root == null) { root = current = new Node(row); continue; } // Traverse up the tree until the parent is found: while (row.ParentNodeId != current.NodeId) { current = current.Parent; } // Add the new node as a child of the current one: var rowNode = new Node(row); rowNode.Parent = current; current.Children.Add(rowNode); current = rowNode; } return root; }