What is the most efficient/elegant way to parse a flat table into a tree?

Question

Assume you have a flat table that stores an ordered tree hierarchy:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

What minimalistic approach would you use to output that to HTML (or text, for that matter) as a correctly ordered, correctly intended tree?

Assume further you only have basic data structures (arrays and hashmaps), no fancy objects with parent/children references, no ORM, no framework, just your two hands. The table is represented as a result set, which can be accessed randomly.

Pseudo code or plain English is okay, this is purely a conceptional question.

Bonus question: Is there a fundamentally better way to store a tree structure like this in a RDBMS?

---

EDITS AND ADDITIONS

To answer one commenter's (Mark Bessey's) question: A root node is not necessary, because it is never going to be displayed anyway. ParentId = 0 is the convention to express "these are top level". The Order column defines how nodes with the same parent are going to be sorted.

The "result set" I spoke of can be pictured as an array of hashmaps (to stay in that terminology). For my example was meant to be already there. Some answers go the extra mile and construct it first, but thats okay.

The tree can be arbitrarily deep. Each node can have N children. I did not exactly have a "millions of entries" tree in mind, though.

Don't mistake my choice of node naming ('Node 1.1.1') for something to rely on. The nodes could equally well be called 'Frank' or 'Bob', no naming structure is implied, this was merely to make it readable.

I have posted my own solution so you guys can pull it to pieces.

Answer 1

Assuming that you know that the root elements are zero, here's the pseudocode to output to text:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
     print a tab
    print curr \n;
    for each child in the table with a parent of curr
     PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

Answer 2

If nested hash maps or arrays can be created, then I can simply go down the table from the beginning and add each item to the nested array. I must trace each line to the root node in order to know which level in the nested array to insert into. I can employ memoization so that I do not need to look up the same parent over and over again.

Edit: I would read the entire table into an array first, so it will not query the DB repeatedly. Of course this won't be practical if your table is very large.

After the structure is built, I must do a depth first traverse through it and print out the HTML.

There's no better fundamental way to store this information using one table (I could be wrong though ;), and would love to see a better solution ). However, if you create a scheme to employ dynamically created db tables, then you opened up a whole new world at the sacrifice of simplicity, and the risk of SQL hell ;).

Answer 3

You can emulate any other data structure with a hashmap, so that's not a terrible limitation. Scanning from the top to the bottom, you create a hashmap for each row of the database, with an entry for each column. Add each of these hashmaps to a "master" hashmap, keyed on the id. If any node has a "parent" that you haven't seen yet, create an placeholder entry for it in the master hashmap, and fill it in when you see the actual node.

To print it out, do a simple depth-first pass through the data, keeping track of indent level along the way. You can make this easier by keeping a "children" entry for each row, and populating it as you scan the data.

As for whether there's a "better" way to store a tree in a database, that depends on how you're going to use the data. I've seen systems that had a known maximum depth that used a different table for each level in the hierarchy. That makes a lot of sense if the levels in the tree aren't quite equivalent after all (top level categories being different than the leaves).

Answer 4

Well given the choice, I'd be using objects. I'd create an object for each record where each object has a children collection and store them all in an assoc array (/hashtable) where the Id is the key. And blitz through the collection once, adding the children to the relevant children fields. Simple.

But because you're being no fun by restricting use of some good OOP, I'd probably iterate based on:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Edit: this is similar to a couple of other entries, but I think it's slightly cleaner. One thing I'll add: this is extremely SQL-intensive. It's nasty. If you have the choice, go the OOP route.

Answer 5

There are several ways to store tree-structured data in a relational database. What you show in your example uses two methods:

• Adjacency List (the "parent" column) and
• Path Enumeration (the dotted-numbers in your name column).

Another solution is called Nested Sets, and it can be stored in the same table too. Read "Trees and Hierarchies in SQL for Smarties" by Joe Celko for a lot more information on these designs.

I usually prefer a design called Closure Table (aka "Adjacency Relation") for storing tree-structured data. It requires another table, but then querying trees is pretty easy.

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Store all paths in the Closure Table, where there is a direct ancestry from one node to another. Include a row for each node to reference itself. For example, using the data set you showed in your question:

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

Now you can get a tree starting at node 1 like this:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

The output (in MySQL client) looks like the following:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

In other words, nodes 3 and 5 are excluded, because they're part of a separate hierarchy, not descending from node 1.

---

Re: comment from e-satis about immediate children (or immediate parent). You can add a "path_length" column to the ClosureTable to make it easier to query specifically for an immediate child or parent (or any other distance).

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

Then you can add a term in your search for querying the immediate children of a given node. These are descendants whose path_length is 1.

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

Answer 6

This was written quickly, and is neither pretty nor efficient (plus it autoboxes alot, converting between int and Integer is annoying!), but it works.

It probably breaks the rules since I'm creating my own objects but hey I'm doing this as a diversion from real work :)

This also assumes that the resultSet/table is completely read into some sort of structure before you start building Nodes, which wouldn't be the best solution if you have hundreds of thousands of rows.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
     this.parent = parent;
     this.children = new ArrayList<Node>();
     this.name = name;
     this.id = id;
    }

    public int getId() {
     return this.id;
    }

    public String getName() {
     return this.name;
    }

    public void addChild(Node child) {
     children.add(child);
    }

    public List<Node> getChildren() {
     return children;
    }

    public boolean isRoot() {
     return (this.parent == null);
    }

    @Override
    public String toString() {
     return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

     // maps id of a node to it's Node object
     Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

     // maps id of a node to the id of it's parent
     Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

     // create special 'root' Node with id=0
     Node root = new Node(null, 0, "root");
     nodeMap.put(root.getId(), root);

     // iterate thru the input
     for (Map<String, String> map : input) {

      // expect each Map to have keys for "id", "name", "parent" ... a
      // real implementation would read from a SQL object or resultset
      int id = Integer.parseInt(map.get("id"));
      String name = map.get("name");
      int parent = Integer.parseInt(map.get("parent"));

      Node node = new Node(null, id, name);
      nodeMap.put(id, node);

      childParentMap.put(id, parent);
     }

     // now that each Node is created, setup the child-parent relationships
     for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
      int nodeId = entry.getKey();
      int parentId = entry.getValue();

      Node child = nodeMap.get(nodeId);
      Node parent = nodeMap.get(parentId);
      parent.addChild(child);
     }

     return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
     printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

     printNode(node, indentLevel);
     // recurse
     for (Node child : node.getChildren()) {
      printNodes(child, indentLevel + 1);
     }
    }

    static void printNode(Node node, int indentLevel) {
     StringBuilder sb = new StringBuilder();
     for (int i = 0; i < indentLevel; i++) {
      sb.append("\t");
     }
     sb.append(node);

     System.out.println(sb.toString());
    }

    public static void main(String[] args) {

     // setup dummy data
     List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
     resultSet.add(newMap("1", "Node 1", "0"));
     resultSet.add(newMap("2", "Node 1.1", "1"));
     resultSet.add(newMap("3", "Node 2", "0"));
     resultSet.add(newMap("4", "Node 1.1.1", "2"));
     resultSet.add(newMap("5", "Node 2.1", "3"));
     resultSet.add(newMap("6", "Node 1.2", "1"));

     Node root = NodeBuilder.build(resultSet);
     printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
     Map<String, String> row = new HashMap<String, String>();
     row.put("id", id);
     row.put("name", name);
     row.put("parent", parentId);
     return row;
    }
}

Answer 7

As of Oracle 9i, you can use CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

As of SQL Server 2005, you can use a recursive common table expression (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Both will output the following results.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

Answer 8

If elements are in tree order, as shown in your example, you can use something like the following Python example:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

What this does is maintain a stack representing the current position in the tree. For each element in the table, it pops stack elements (closing the matching divs) until it finds the parent of the current item. Then it outputs the start of that node and pushes it to the stack.

If you want to output the tree using indenting rather than nested elements, you can simply skip the print statements to print the divs, and print a number of spaces equal to some multiple of the size of the stack before each item. For example, in Python:

print "  " * len(stack)

You could also easily use this method to construct a set of nested lists or dictionaries.

Edit: I see from your clarification that the names were not intended to be node paths. That suggests an alternate approach:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

This constructs a tree of arrays of tuples(!). idx[0] represents the root(s) of the tree. Each element in an array is a 2-tuple consisting of the node itself and a list of all its children. Once constructed, you can hold on to idx[0] and discard idx, unless you want to access nodes by their ID.

Answer 9

If you use nested sets (sometimes referred to as Modified Pre-order Tree Traversal) you can extract the entire tree structure or any subtree within it in tree order with a single query, at the cost of inserts being more expensive, as you need to manage columns which describe an in-order path through thee tree structure.

For django-mptt, I used a structure like this:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

Which describes a tree which looks like this (with id representing each item):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

Or, as a nested set diagram which makes it more obvious how the lft and rght values work:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

As you can see, to get the entire subtree for a given node, in tree order, you simply have to select all rows which have lft and rght values between its lft and rght values. It's also simple to retrieve the tree of ancestors for a given node.

The level column is a bit of denormalisation for convenience more than anything and the tree_id column allows you to restart the lft and rght numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft and rght columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.

In terms of actually working with this data to display a tree, I created a tree_item_iterator utility function which, for each node, should give you sufficient information to generate whatever kind of display you want.

More info about MPTT:

• Trees in SQL
• Storing Hierarchical Data in a Database
• Managing Hierarchical Data in MySQL

Answer 10

Here is how I do it currently: (This solution assumes you actually can index into the result set, as indicated in the question.)

• Make sure the result set is "ORDER BY Order" so all nodes with the same parent come out in the right order.

• Iterate the result set, write down each row index (not node Id!) in a hashmap children, keyed by ParentId:

  {0:[1,3], 1:[2,6], 2:[4], 3:[5]}

• Depth-first recurse into children, starting with the default parent node "0". The row index in the child array is used to pull out any other information from the result set.

• Maintain info about the row index and its nesting level (e.g. recursion depth), building this array (let's call it sequence):

  [{row:1,lvl:0}, {row:2,lvl:1}, {row:4,lvl:2}, {row:6,lvl:1}, {row:3,lvl:0}, {row:5,lvl:1}]

• Use that array to access the result set sequentially (simple loop) any time I need to print out the tree. Assuming I have to do it more than once, I spare me the repeated recursion.

Pseude-Code:

children = {}

foreach row in resultSet
  parentId = row.fields['ParentId']
  if parentId not in children
    children[parentId] = []
  end if
  chidren[parentId].push(row.index)
next row

function buildSequence(parentId = 0, depth = 0)
  sequence = []
  foreach rowIndex in children[parentId]
    sequence.push( {row: rowIndex, lvl: depth} )
    thisId = resultSet[rowIndex].fields['Id']
    if thisId in children
      sequence.append( buildSequence(thisId, depth + 1) )
    end if
  next rowIndex
  return sequence
end function

sequence = buildSequence()

Answer 11

I find good article about this http://www.alberton.info/talks