Flatten a multilevel linked list

Question

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<T> {
    Nodes<T> right;
    T item;
    Nodes<T> down;

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

public final class FlattenMultiLevelList<T> {


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

        // travese the all heads
        while (!nodeHead.isEmpty()) {
            Nodes<T> 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<Integer> node1_1_1 = new Nodes<>(10);
        Nodes<Integer> node1_1_2 = new Nodes<>(5);
        Nodes<Integer> node1_1_3 = new Nodes<>(12);
        Nodes<Integer> node14 = new Nodes<>(7);
        Nodes<Integer> node15 = new Nodes<>(11);

        node1_1_1.right = node1_1_2;
        node1_1_2.right = node1_1_3;
        node1_1_3.right = node14;
        node14.right = node15;

        // level 2, first linkedlist, first node
        Nodes<Integer> node2_1_1 = new Nodes<>(4);
        Nodes<Integer> node2_1_2 = new Nodes<>(20);
        Nodes<Integer> node2_1_3 = new Nodes<>(13);

        node2_1_1.right = node2_1_2;
        node2_1_2.right = node2_1_3;
        node1_1_1.down = node2_1_1;

        // level 2, second linkedlist, first node.
        Nodes<Integer> node2_2_1 = new Nodes<>(17);
        Nodes<Integer> node2_2_2 = new Nodes<>(6);
        node2_2_1.right = node2_2_2;
        node1_1_3.down = node2_2_1;


        Nodes<Integer> node3_1_1 = new Nodes<>(2);
        node2_1_2.down = node3_1_1;

        Nodes<Integer> node3_2_1 = new Nodes<>(16);
        node2_1_3.down = node3_2_1;

        Nodes<Integer> node3_3_1 = new Nodes<>(9);
        Nodes<Integer> node3_3_2 = new Nodes<>(8);
        node3_3_1.right = node3_3_2;
        node2_2_1.down = node3_3_1;

        Nodes<Integer> node4_1_1 = new Nodes<>(3);
        node3_2_1.down = node4_1_1;


        Nodes<Integer> node4_2_1 = new Nodes<>(19);
        Nodes<Integer> node4_2_2 = new Nodes<>(15);
        node4_2_1.right = node4_2_2;
        node3_3_1.down = node4_2_1;


        assertEquals(Arrays.asList(10,5,12,7,11,4,20,13,17,6,2,16,9,8,3,19,15), FlattenMultiLevelList.flatten(node1_1_1));
    }

}

Answer 1

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 <T> List<T> flatten(Nodes<T> node) {
    final List<T> flattenedList = new ArrayList<>();
    final Queue<T> remainingTraversalHeads = new LinkedList<>();
    remainingTraversalHeads.add(node);

    while (!remainingTraversalHeads.isEmpty()) {
        Nodes<T> 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.

Answer 2

@Vogel612 has pretty much got everything covered.

The only change I'd make is to add commentary with regards to input and output parameters...

And I'd rename the argument from node to headNode or head because you don't just want any node, you want the head node so you can flatten the entire list. Any nodes not under the supplied node wouldn't get flattened.