Hydrate a tree from a table

Question

I have a DataTable with all of my nodes in it. They were serialized to database. I want to create an object graph (hierarchical) representation of the data. There seem to be a few methods for doing this.

This article describes a high order method (meaning it involves lots of searching of the DataTable before the tree is fully built)

Is there an Order-N approach? In my case, I have pre-sorted the nodes of the tree in the DataTable into the in-order form. Meaning, the first row shows a NULL for the parent, because it's the root. Each subsequent row is sorted in in-order notation.

I seem to recall an Order-N approach from my school days. But I can't remember.

My DataTable schema resembles this:

NodeID - int
ParentNodeId - nullable
Data - string

Possibly related: http://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure That uses a dictionary to keep track of the parent nodes, and is probably the easiest way to do it. I've used a recursive solution that doesn't require a dictionary, but it's been so long I'd have to derive it again. — Jim Mischel, Oct 23 '11 at 03:56
That doesn't look like in-order form. If that were the case, root wouldn't be the first node in the table. Did you mean pre-order? — svick, Oct 23 '11 at 17:27

Scott Rippey · Accepted Answer · 2011-10-24T04:46:22.027

Here's an algorithm that should do what you need it to do. It assumes your data is in order, so it performs 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) { ... }
}

Load first row as current.
Load next row; compare newRow.ParentNodeId to current.NodeId.
Until you find a match, set current = current.Parent
Add the newRow to current.Children and set current to the new row.
Go to step 2.

That's it! If your data is guaranteed to be structured correctly, then you won't need to do any extra null checks.

Sample:

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;
}

Thanks! Got a little issue. In the Node class, you've got Parent listed as a fully formed Node. All I have is the Parent's ID. In order to fully form the parent Node, I have to perform a search of the DataTable for each Node. So we're back to that again -- extra lookups. What's coming from my database is a column that tells me the Parent's ID. The rows are in-order. — 101010, Oct 23 '11 at 13:16
Sorry, I forgot a line: `rowNode.Parent = current;`. For each new row, we traverse up the tree, looking for a matching `ParentNodeId`. Then, the new `rowNode.Parent` is set to `current`. — Scott Rippey, Oct 24 '11 at 04:18
... Since the data is "in-order", we know that the `ParentNodeId` must match one of `current`'s ancestors. That's what gives us `O(n)`! — Scott Rippey, Oct 24 '11 at 04:21

Hydrate a tree from a table

1 Answers1