Sort a SQL query with id and parentid so that the rows have the correct order of the tree.

README.md

_queryTreeSort

Note: Please check this blog post for more details on these functions.

Sort a SQL query with id and parentid so that the rows have the correct order of the tree.

Parameters:

• q (Array): A query result (see example below)
• id (String): The name of the id column (Default: "id")
• parentid (String): The name of the ParentItemID column (Default: "parentid")

Example:

SQL: SELECT * FROM Animals ORDER BY name

_queryTreeSort({q: [
	{"id": 456, "parentid": 123, "name": "Dogs"},
	{"id": 214, "parentid": 456, "name": "Labradors"},
	{"id": 123, "parentid": 0, "name": "Mammals"},
	{"id": 810, "parentid": 456, "name": "Pugs"},
	{"id": 919, "parentid": 456, "name": "Terriers"}
]});

Result:

[
	{"id": 123, "parentid": 0, "name": "Mammals"},
	{"id": 456, "parentid": 123, "name": "Dogs"},
	{"id": 214, "parentid": 456, "name": "Labradors"},
	{"id": 810, "parentid": 456, "name": "Pugs"},
	{"id": 919, "parentid": 456, "name": "Terriers"}
]

What now?

Use the result to loop over the query or create a tree with _makeTree()

_makeTree

Transform a correctly sorted SQL query with id and parentid into a tree object. Use _queryTreeSort() to sort you SQL query.

Parameters:

• q (Array): A query result (see example below)
• id (String): The name of the id column (Default: "id")
• parentid (String): The name of the ParentItemID column (Default: "parentid")
• children (String): The name of the "children" array to be created in rows that have children (Default: "children")

Example:

_makeTree({ q:
	[
		{"id": 123, "parentid": 0, "name": "Mammals"},
		{"id": 456, "parentid": 123, "name": "Dogs"},
		{"id": 214, "parentid": 456, "name": "Labradors"},
		{"id": 810, "parentid": 456, "name": "Pugs"},
		{"id": 919, "parentid": 456, "name": "Terriers"}
	]
});

Result:

[
	{
		"id": 123,
		"parentid": 0,
		"name": "Mammals",
		"children": [
			{
				"id": 456,
				"parentid": 123,
				"name": "Dogs",
				"children": [
					{
						"id": 214,
						"parentid": 456,
						"name": "Labradors"
					},
					{
						"id": 810,
						"parentid": 456,
						"name": "Pugs"
					},
					{
						"id": 919,
						"parentid": 456,
						"name": "Terriers"
					}
				]
			}
		]
	}
]

What now?

Use the result to display your tree with a recursive function like _renderTree()

_makeTree.coffee

_makeTree = (options) ->
	id = options.id or "id"
	pid = options.parentid or "parentid"
	children = options.children or "children"

	temp = {}
	o = []

	# Create the tree
	for e in options.q
		e[children] = []
		# Add the row to the index
		temp[e[id]] = e
		# This parent should be in the index
		if temp[e[pid]]?
			# This row is a child
			# Add the child to the parent
			temp[e[pid]][children].push(e)
		else
			# Add a root item
			o.push(e)
	return o

_makeTree.js

var _makeTree = function(options) {
  var children, e, id, o, pid, temp, _i, _len, _ref;
  id = options.id || "id";
  pid = options.parentid || "parentid";
  children = options.children || "children";
  temp = {};
  o = [];
  _ref = options.q;
  for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    e = _ref[_i];
    e[children] = [];
    temp[e[id]] = e;
    if (temp[e[pid]] != null) {
      temp[e[pid]][children].push(e);
    } else {
      o.push(e);
    }
  }
  return o;
};

_queryTreeSort.coffee

_queryTreeSort = (options) ->
	id = options.id or "id"
	pid = options.parentid or "parentid"
	ri  = [] # Root items
	rfi = {} # Rows from id
	cfi = {} # Children from id
	o = []
	# Setup Indexing
	for e, i in options.q
		rfi[e[id]] = i
		if not cfi[e[pid]]?
			cfi[e[pid]] = []
		cfi[e[pid]].push(options.q[i][id])
	# Find parents without rows
	for e in options.q when not rfi[e[pid]]?
		ri.push(e[id])

	# Create the correct order
	while ri.length
		thisid = ri.splice(0,1)
		o.push(options.q[rfi[thisid]])

		if cfi[thisid]?
			ri = cfi[thisid].concat(ri)
	return o

_queryTreeSort.js

var _queryTreeSort = function(options) {
  var cfi, e, i, id, o, pid, rfi, ri, thisid, _i, _j, _len, _len1, _ref, _ref1;
  id = options.id || "id";
  pid = options.parentid || "parentid";
  ri = [];
  rfi = {};
  cfi = {};
  o = [];
  _ref = options.q;
  for (i = _i = 0, _len = _ref.length; _i < _len; i = ++_i) {
    e = _ref[i];
    rfi[e[id]] = i;
    if (cfi[e[pid]] == null) {
      cfi[e[pid]] = [];
    }
    cfi[e[pid]].push(options.q[i][id]);
  }
  _ref1 = options.q;
  for (_j = 0, _len1 = _ref1.length; _j < _len1; _j++) {
    e = _ref1[_j];
    if (rfi[e[pid]] == null) {
      ri.push(e[id]);
    }
  }
  while (ri.length) {
    thisid = ri.splice(0, 1);
    o.push(options.q[rfi[thisid]]);
    if (cfi[thisid] != null) {
      ri = cfi[thisid].concat(ri);
    }
  }
  return o;
};

_renderTree.coffee

_renderTree = (tree) ->
	html = "<ul>"
	for e in tree
		html += "<li>#{e.name}"
		if e.children?
			html += _renderTree(e.children)
		html += "</li>"
	html += "</ul>"
	return html

_renderTree.js

var _renderTree = function(tree) {
  var e, html, _i, _len;
  html = "<ul>";
  for (_i = 0, _len = tree.length; _i < _len; _i++) {
    e = tree[_i];
    html += "<li>" + e.name;
    if (e.children != null) {
      html += _renderTree(e.children);
    }
    html += "</li>";
  }
  html += "</ul>";
  return html;
};

To Speed up the raw Make Tree it's also possible to do the makeTree without the presorting.
Just use this version of _makeTree:

_makeTree = (options) ->
    id = options.id or "id"
    pid = options.parentid or "parentid"
    children = options.children or "children"

    # create the index
    temp = {}
    for e in options.q
        # predefine the childs array
        e[children] = []
        # write the id index to find by parentid in second loop
        temp[e[id]] = e

    # Create the tree
    o = []
    for e in options.q
        # This parent should be in the index
        if temp[e[pid]]?
            # This row is a child
            # Add the child to the parent
            temp[e[pid]][children].push(e)
        else
            # Add a root item
            o.push(e)
    return o

If someone needs... Tree to Array:

var _flatTree = function(options) {
    var id, pid, children, parentNodeId, tree, output, entry, entryChildren;
    id = options.id || "id";
    pid = options.parentid || "parentid";
    children = options.children || "children";
    parentNodeId = options.parentnodeid || null;
    tree = options.tree;
    output = [];

    for (var i = 0; i < tree.length; i++)
    {
        entry = tree[i];
        entryChildren = entry[children];

        delete entry[children];

        if(entry[pid] == undefined) entry[pid] = parentNodeId;

        output.push(entry);

        if((entryChildren != null) && (entryChildren.length > 0))
        {
            var flat = _flatTree({tree:entryChildren, parentid:pid, parentnodeid:entry[id], children:children});
            for (var j = 0; j < flat.length; j++) output.push(flat[j]);
        }
    }

    return output;
};