tree.js

/*
var messages = [
  { id: 1, inReplyTo: 2 },
  { id: 2 },
  { id: 3, inReplyTo: 1 },
  { id: 4, inReplyTo: 999 },
  { id: 5, inReplyTo: 6 },
  { id: 6, inReplyTo: 3 },
  { id: 7, inReplyTo: 6 },
  { id: 8, inReplyTo: 6 },
];
*/

var messages = [
    { id: 1 }
];

for (var i = 1; i < 70000; i++) {
  messages.push({ id: i+1, inReplyTo: i});
}

function Node(id, ref) {
  this.id = id;
  this.ref = ref;
  this.children = [];
}

Node.prototype.indexOf = function(id) {
  if (this.id === id) return 0;

  for (var i = 0; i < this.children.length; i++) {
    if (this.children[i].id === id) return i;
  }

  return -1;
}

var tree = [];

function isRootNode(msg) {
  if (!('inReplyTo' in msg)) return true;

  for (var i = 0; i < messages.length; i++) {
    if (messages[i].id === msg.inReplyTo) return false;
  }

  return true;
}

// Collect root nodes:
for (var i = 0; i < messages.length; i++) {
  var msg = messages[i];
  if (isRootNode(msg)) {
    tree.push(new Node(msg.id));
  }
}

// Remove root nodes from the input array:
for (var i = 0; i < tree.length; i++) {
  for (var j = 0; j < messages.length; j++) {
    if (tree[i].id === messages[j].id) {
      messages.splice(j, 1);
      j--;
    }
  }
}

// Sort non-root nodes onto root nodes:
while (messages.length) {
  for (var i = 0; i < tree.length; i++) {
    var root = tree[i];
    for (var j = 0; j < messages.length; j++) {
      var msg = messages[j];
      if (~root.indexOf(msg.inReplyTo)) {
        root.children.push(new Node(msg.id, msg.inReplyTo));
        messages.splice(j, 1);
        j--;
      }
    }
  }
}


// Sort child nodes after their reference:
for (var i = 0; i < tree.length; i++) {
  var root = tree[i];
  var children = root.children.slice(0);

  for (var j = 0; j < children.length; j++) {
    var child = children[j];
    var index = root.indexOf(child.ref);

    root.children.splice(j, 1);
    root.children.splice(index, 0, child);
  }

  root.children.reverse();
}

//console.log(JSON.stringify(tree, null, 2));