Sorting root nodes for trees algorithm

Question

I am trying to figure out an algorithm to solve this problem:

I have a unsorted array, which contains nodes that will be used to build several non-binary trees. These nodes have a name, an id, and knowledge of who their parent is.

So currently these trees are built and just connect the root nodes to their descendants and display them in whatever order they were created.

So you would have the first tree with all of it's descendant followed by the next tree that happened to appear next in the original array connected with it's descendant and so on.

I need to alphabetically sort the root nodes so that the first tree is the node with the earliest name in the dictionary connected to it's descendants followed by the next one.

So I am essentially sorting trees themselves and not all nodes. The non-root nodes should NOT be sorted. So you can say if the node's parent is "null" then it is a root node.

NOTE: Programming in Javascript/Angular

This isn't clear. You're basically saying you want to apply a sort to a subset of the elements in an array? — Oliver Charlesworth, Aug 24 '16 at 22:54
@OliverCharlesworth: Yes, given a set of nodes in an array only sort the ones that are considered "root nodes". — M. Slomski, Aug 25 '16 at 12:19

Jim Mischel · Accepted Answer · 2016-08-25T16:56:31.100

Seems like you could write a comparison function to do that for you. You don't say what language you're using, but I think you can glean the gist of it from this:

int Compare(Node node1, Node node2)
{
    if (node1.Parent == null and node2.Parent == null)
    {
        // two root nodes. Compare their names.
        return node1.Name.CompareTo(node2.Name);
    }

    if (node1.Parent == null)
    {
        // node1 is a root node and node2 isn't.
        // node1 sorts first.
        return -1;
    }

    if (node2.Parent == null)
    {
        // node2 is a root node and node1 isn't.
        // node2 sorts first.
        return 1;
    }

    // neither is a root node, so they're considered equal.
    return 0;
}

That would sort it so that you have:

root1
root2
root3
(other roots)
all children

Now, if you want the array sorted so that you have:

root1
child of root1
child of root1
child of root1
root2
child of root2
child of root2
root3
...

Then you modify that comparison. The root node comparison stays the same. When you're comparing two child nodes, you compare their parent nodes' names. When comparing a root node against a child, you compare the root node's name against the child's parent's name. Oh, and you have to special-case when a child node is compared against its own parent.

Updated to mention what is being used but the logic should be similar, right? — M. Slomski, Aug 25 '16 at 03:28
@M.Slomski: Yes, logic is similar. See http://stackoverflow.com/questions/5002848/how-to-define-custom-sort-function-in-javascript for an example of defining a custom comparator for a Javascript sort. — Jim Mischel, Aug 25 '16 at 11:52

Sorting root nodes for trees algorithm

1 Answers1