I have a tree structure of objects (JavaScript/TypeScript), all derived of the same class (T). Each object may or may not contain children of the same object (List). Therefore those children may or may not contain their own children (List), and so on...

I'm needing to sort each of these "levels" of nodes by a specific property of the object.

Currently I'm handling only each parent and their children:

                    nodes.sort((a, b) => {
                        return a.Id- b.Id;
                    });                       

                    nodes.forEach(function (node) {
                        node.children.sort((a, b) => {
                            return a.Id- b.Id;
                        });
                    });

However, I'm needing a method that will sort all children of children, children of those children, and etc. I imagine this will involve recursion, but I'm not sure the best way of handling this in terms of efficiency.

I have a tree structure of objects (JavaScript/TypeScript), all derived of the same class (T). Each object may or may not contain children of the same object (List). Therefore those children may or may not contain their own children (List), and so on...

I'm needing to sort each of these "levels" of nodes by a specific property of the object.

Currently I'm handling only each parent and their children:

                    nodes.sort((a, b) => {
                        return a.Id- b.Id;
                    });                       

                    nodes.forEach(function (node) {
                        node.children.sort((a, b) => {
                            return a.Id- b.Id;
                        });
                    });

However, I'm needing a method that will sort all children of children, children of those children, and etc. I imagine this will involve recursion, but I'm not sure the best way of handling this in terms of efficiency.

• javascript
• sorting
• recursion
• typescript

• 1 There's no efficiency involved here. You need to sort N independant lists. That's O(N). Use recursion. – Amit Commented Jul 23, 2015 at 21:13
• @Amit O(N) for each list you say! – Fals Commented Jul 23, 2015 at 21:15
• 2 @Fals I meant O(N) where N is the number of lists ("children"). The sorting itself is not shown so I can't assume anything about the type of sorting used, but obviously every list has to be sorted as well. – Amit Commented Jul 23, 2015 at 21:17
• If there is not a more efficient way, then my biggest issue with understanding this is syntax. – cdalto Commented Jul 23, 2015 at 21:20
• As you already know you will need recursion for this, have you tried implementing it? Please show us your approach. – Bergi Commented Jul 23, 2015 at 21:24

1 Answer 1

a) Sort the nodes.

b) Go through each node, if the node has children, repeat step A with its children.

function sortNodesAndChildren(nodes) {
    nodes.sort();
    nodes.forEach(function (node) {
        if (nodeHasChildren(node)) {
            sortNodesAndChildren(node.children);
        }
    })
}