Sort array of objects with hierarchy by hierarchy and name

I have an array of nested objects:

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

I need to sort them in the way for nodes at same level will be sorted by alphabetic order (asc/desc configurable) and all child nodes should be after their parent and before their parent's sibling node also sorted by alphabetic order.

For example, if sorted by asc, the output should be

[ 
    { _id: 4, parent: 0, name: 'A' },
    { _id: 5, parent: 4, name: 'M' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 3, parent: 1, name: 'Z' } 
]

In the output, 4 is before 1 because A < Z. 5 and 6 are sorted alphabetically under 4 and before 1. Similar case for 8 and 7 under 2 and before 3.

and if desc, the output should be:

[ 
    { _id: 1, parent: 0, name: 'Z' },
    { _id: 3, parent: 1, name: 'Z' },
    { _id: 2, parent: 1, name: 'H' },
    { _id: 7, parent: 2, name: 'L' },
    { _id: 8, parent: 2, name: 'G' },
    { _id: 4, parent: 0, name: 'A' },
    { _id: 6, parent: 4, name: 'N' },
    { _id: 5, parent: 4, name: 'M' }
]

I tried to implement a function as below.

```
function sortByHierarchyAndName(arr, sort) {
var i = 0;
j = 0;
t = 0;
parentFound = false;
x = arr.length;
arr2 = [];

//Sort by parent asc first
arr = arr.sort(function(a, b) {
if(a.parent b.parent) return 1;
return 0;
});

for(; i = arr2[j].name) arr2.splice(j, 0, arr[i]);
} else {
if(arr[i].name = arr2[j].name) {
arr2.splice(j, 0, arr[i]);

Since you have a representation of a tree i suggest using it,
then traverse it in pre-order

So if

[
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]

lets build a tree like this

[
      {_id:1, parent:0, name:'Z', children: 
         [
             {_id:2, parent:1, name:'H', children: 
                [
                   {_id:8, parent:2, name:'G', children: []},
                   {_id:7, parent:2, name:'L', children: []}
                ]
             },
             {_id:3, parent:1, name:'Z', children: []}
         ]
      },
      {_id:4, parent:0, name:'A', children: 
         [
             {_id:5, parent:4, name:'M', children: []},
             {_id:6, parent:4, name:'N', children: []}
         ]},
   ]

my suggestion is like this:

var nodes = [
    {_id:1, parent:0, name:'Z'},
    {_id:4, parent:0, name:'A'},
    {_id:2, parent:1, name:'H'},    
    {_id:8, parent:2, name:'G'},        
    {_id:5, parent:4, name:'M'},
    {_id:6, parent:4, name:'N'},
    {_id:3, parent:1, name:'Z'},
    {_id:7, parent:2, name:'L'}
]
var tree = {_id:0};

var addChildrenToNode = function(node,cmp){
    var currentNodeId = node._id;
    node.children = [];
    nodes.forEach(function(e){
        if(e.parent === currentNodeId){
            e = addChildrenToNode(e);
            node.children.push(e);
        }
    });
    node.children = node.children.sort(cmp); // sort the children
    return node;
};

var cmp = function(a, b) { 
    if(a.name  b.name) return 1; 
    return 0; 
};
tree = addChildrenToNode(tree,cmp);

Then you only have to do the pre-order traverse, like this:

var preOrderTraverse = function(node, fn){ // sends values of tree to fn in pre-order
    fn(node); //call at preorder
    if(node.children.length > 0){
        node.children.forEach(function(e){
            preOrderTraverse(e,fn);
        });
    }
}

preOrderTraverse(tree,
    function(node){ // do what you like with each node
        console.log(node);
    }
);

StackExchange Code Review Q#119574, answer score: 4