I've got a DataTable wonderful my nodes inside it. These were serialized to database. I wish to create an item graph (hierarchical) representation from the data. There appear to become a couple of techniques for carrying this out.

This article describes a high order method (meaning it calls for plenty of searching from the DataTable prior to the tree is fully built)

Can there be a purchase-N approach? During my situation, I've pre-sorted the nodes from the tree within the DataTable in to the in-order form. Meaning, the very first row shows a NULL for that parent, since it is the main. Each subsequent row is sorted in in-order notation.

I appear to recall a purchase-N approach from the school days. However I can't remember.

My DataTable schema resembles this:

  • NodeID - int
  • ParentNodeId - nullable
  • Data - string

Here's an formula which should do the thing you need it to complete. It assumes your computer data is needed, therefore it works in O(n).

First, you'll need a node that appears such as this:

class Node {
    Node Parent;
    List<Node> Children = new List<Node>();
    int NodeId;
    string Data;
    public Node(NodeRow row) { ... }
  1. Load first row as current.
  2. Load next row compare newRow.ParentNodeId to current.NodeId.
  3. Until you get a match, set current = current.Parent
  4. Add the newRow to current.Children and hang current towards the new row.
  5. Visit step two.

There you have it! In case your information is certain to be structured properly, then you definitely will not have to do any other null inspections.


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);
        // 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 = rowNode;
    return root;