Sort by a hierarchy

I came across this problem a few weeks ago and when I searched for a solution, I couldn't find one. As it turns out, it's a pretty straightforward algorithms application once you see how to do it; I thought it was interesting enough to share.

I had an unsorted list of records that were related by an arbitrary number of parent-child relations. I wanted to present the list with the unparented records first, with their children beneath them, their children beneath them, etc. So, given a list like:

Id Name Parent

0009 Piotr Nickolevitch 0007

0001 Charles Xavier

0008 James Logan 0007

0013 James Proudstar 0007

0014 Eric Lensherr

0005 Bobby Drake 0002

0007 Ororo Munroe 0001

0012 Kurt Wagner 0007

0010 Kitty Pryde 0007

0003 Jean Grey 0002

0002 Scott Summers 0001

0004 Warren Worthington 0002

0006 Hank McCoy 0002

0011 Lockheed 0010

I'd want to sort the output to appear as:

Charles Xavier
- Scott Summers
  - Jean Grey
  - Warren Worthington
  - Bobby Drake
  - Hank McCoy
- Ororo Munroe
  - James Logan
  - Piotr Nickolevitch
  - Kitty Pryde
    - Lockheed
  - Kurt Wagner
  - James Proudstar
Eric Lensherr

So in essence, transform a table into a tree. I can't properly "sort" this but instead I have to do two passes through the list keeping track of which elements are associated with which ID values and then go through determining the children. So, if my data is an array of JavaScript objects with properties Id, Name, and Boss, my first pass will be:


var idsToElements = {};
for (var i = 0; i < input.length; i++)  {
    idsToElements[input[i].Id] = input[i];
}

Listing 1: Pass one; record the positions of all the Ids

This just gives me a quick lookup of Ids to the actual elements that they represent. Now, go through the main list and create a sublist of each element's children in-place:


var topLevel = [];

for (var i = 0; i < input.length; i++) {
  if (input[i].Boss)  {
    var parentElement = idsToElements[input[i].Boss];
    if (!parentElement) {
      // Parent element missing in list; treat as top-level
      topLevel.push(input[i]);
    } else  {
      if (!parentElement.children)  {
        parentElement.children = [];
      }
      parentElement.children.push(input[i]);
    }
  } else  {
    topLevel.push(input[i]);
  }
}

Listing 2: Pass two; create a children array on each element

Figure 1: parent/child relationships discovered dynamically

As I encounter each element, I find its parent (by Id) in the hash structure I created in listing 1. Then I append the element to the children array on the parent element. If it doesn't have a parent element, it goes into the new de-facto parent topLevel. Now, topLevel is an array of the elements that either a) didn't have parent records or b) had parent records, but those parent records weren't found (depending on the application, this may or may not represent an error condition). Since each parent has an array of children, each can be sub-sorted if necessary. They can be output in a hierarchy via:

function traverse(list)  {
  var html = '<ul>';
  for (var i = 0; i < list.length; i++) {
    html += '<li>' + list[i].Name;
    if (list[i].children) {
      html += traverse(list[i].children);
    }
    html += '</li>';
  }
  html += '</ul>';

  return html;
}

html = traverse(topLevel);
document.write(html); // Or $('document.body').append(html), if you're into that sort of thing.

Listing 3: depth-first traversal of the newly created tree structure

I can further generalize this by replacing the hardcode property Boss in listing 2 with a dynamic reference to the parent field, as in:


var topLevel = [];
var parentFieldName = 'Boss';

for (var i = 0; i < input.length; i++) {
  if (input[i][parentFieldName])
    var parentElement = idsToElements[input[i][parentFieldName]]
    if (!parentElement) {
      // Parent element missing in list; treat as top-level
      topLevel.push(input[i]);
    } else  {
      if (!parentElement.children)  {
        parentElement.children = [];
      }
      parentElement.children.push(input[i]);
    }
  } else  {
    topLevel.push(input[i]);
  }
}

Listing 4: More flexible sort routine

Simple enough once you realize that you're looking at a tree structure, but you have to realize what you're looking at first.

Add a comment:

Completely off-topic or spam comments will be removed at the discretion of the moderator.

You may preserve formatting (e.g. a code sample) by indenting with four spaces preceding the formatted line(s)

Command Line Fanatic

Sort by a hierarchy

Add a comment:

Past Posts