Flatten a multilevel linked list

Given such a structure the output should be

10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15.

Given a linked list where in addition to the next pointer, each node
has a child pointer, which may or may not point to a separate list.
These child lists may have one or more children of their own, and so
on, to produce a multilevel data structure, as shown in below
figure.You are given the head of the first level of the list. Flatten
the list so that all the nodes appear in a single-level linked list.
You need to flatten the list in way that all nodes at first level
should come first, then nodes of second level, and so on.

This question is attributed to GeekForGeeks. Looking for code-review, optimizations and best practices. Verifying complexity to be \$O(n)\$, where \$n\$ is the count of all the nodes in the input multilevel linked list.

```
class Nodes {
Nodes right;
T item;
Nodes down;

Nodes(T item) {
this.item = item;
}
}

public final class FlattenMultiLevelList {

public static List flatten (Nodes node) {
final List flattenedList = new ArrayList<>();
final Queue> nodeHead = new LinkedList<>();
nodeHead.add(node);

// travese the all heads
while (!nodeHead.isEmpty()) {
Nodes currNode = nodeHead.poll();
// traverse all Linkedlists
while (currNode != null) {
if (currNode.down != null) { nodeHead.add(currNode.down); }

flattenedList.add(currNode.item);
currNode = currNode.right;
}
}

return flattenedList;
}
}

public class FlattenMultiLevelListTest {

@Test
public void test() {
// level 1 should contain only a single linkedlist.
Nodes node1_1_1 = new Nodes<>(10);
Nodes node1_1_2 = new Nodes<>(5);
Nodes node1_1_3 = new Nodes<>(12);
Nodes node14 = new Nodes<>(7);
Nodes node15 =

What you have here is a right-only in order traversal of your "tree". This means you will have to FIFO-Queue the discovered down nodes to continue from, when you can't traverse right anymore.

Your code nicely reflects this, but I have some comments, especially concerning style and naming:

if (currNode.down != null) { nodeHead.add(currNode.down);  }

IMO you put too much in this line at once, especially when your currNode cannot be nicely read out loud.

I do this as a sanity check for my variable names:

read them out loud, when you can't the name is gruesome,

when it sounds silly, the name is bad,

and only when you can read your complete variable name, without sounding Czech, your names are good.

In accordance to that "policy" I'd rename currNode to currentNode or even better traversalNode.

Something similar goes for your nodeHead. I set as a goal for myself:


If anybody (not even programmer) can read the name, and instantly tell what the variable, class, interface [...] does, it's good. If a programmer can read the name and instantly tell, it's acceptable, all other names are subject to renaming.

If you hadn't provided the nice graphic, I'd have no clue what nodeHead does.

I'd rename to remainingTraversalHeads or something similar.

Additionally to already made points I personally prefer having blocks separate.

The code from above becomes:

if (traversalNode.down != null) {
    remainingTraversalHeads.add(traversalNode.down);
}

With just these two renames, a little styling and the comments removed, your flatten method becomes:

public static  List flatten(Nodes node) {
    final List flattenedList = new ArrayList<>();
    final Queue remainingTraversalHeads = new LinkedList<>();
    remainingTraversalHeads.add(node);

    while (!remainingTraversalHeads.isEmpty()) {
        Nodes traversalNode = remainingTraversalHeads.poll();
        while (traversalNode != null) {
            if (traversalNode.down != null) {
                 remainingTraversalHeads.add(traversalNode.down);
            }
            flattenedList.add(traversalNode.item);
            traversalNode = traversalNode.right;
        }
    }
    return flattenedList;
}

This code IMO is more obvious in it's intention and behaviour.

If I got it right, then this is in fact \$O(n)\$ complexity.

StackExchange Code Review Q#57723, answer score: 6