Flattening hierarchies using stream concatenation vs. parallelism

Question

Consider the following class that represents a single node in a parent-child unidirectional hierarchy:

public class Component {

  private final int value;
  private final List<Component> children;

  public Component(int value) {
    this.value = value;
    this.children = new ArrayList<>();
    System.out.println("Created: " + this);
  }

  public Component child(Component child) {
    this.children.add(child);
    return this;
  }

  public Stream<Component> asFlatStream() {
    return Stream.concat(Stream.of(this),
        children.stream().flatMap(Component::asFlatStream));
  }

  public List<Component> asFlatList() {
    List<Component> flat = new ArrayList<>();
    return asFlatListInternal(flat);
  }

  public List<Component> asFlatListInternal(List<Component> flat) {
    flat.add(this);
    for (Component child : children) {
      child.asFlatListInternal(flat);
    }
    return flat;
  }

  @Override
  public String toString() {
    return String.valueOf(value);
  }

  public static void main(String[] args) {
    Component root = new Component(0)
        .child(new Component(1)
            .child(new Component(5))
            .child(new Component(6))
            .child(new Component(7)
                .child(new Component(8))))
        .child(new Component(2)
            .child(new Component(9))
            .child(new Component(10)))
        .child(new Component(3))
        .child(new Component(4));

    Supplier<Stream<Component>> streamSupplier = () -> root.asFlatStream();
    System.out.print("Sequential as stream: ");
    streamSupplier.get()
        .peek(c -> System.out.print(c + " "))
        .forEach(c -> { });
    System.out.print("\n  Parallel as stream: ");
    streamSupplier.get().parallel()
        .peek(c -> System.out.print(c + " "))
        .forEach(c -> { });

    System.out.print("\n  Sequential as list: ");
    root.asFlatList().stream()
        .peek(c -> System.out.print(c + " "))
        .forEach(c -> { });
    System.out.print("\n  Parallel as list: ");
    root.asFlatList().stream().parallel()
        .peek(c -> System.out.print(c + " "))
        .forEach(c -> { });
  }

}

A possible output of a single run:

Created: 0
Created: 1
Created: 5
Created: 6
Created: 7
Created: 8
Created: 2
Created: 9
Created: 10
Created: 3
Created: 4
Sequential as stream: 0 1 5 6 7 8 2 9 10 3 4 
  Parallel as stream: 1 5 6 7 8 2 0 9 10 3 4 
  Sequential as list: 0 1 5 6 7 8 2 9 10 3 4 
    Parallel as list: 2 9 8 10 1 0 7 6 4 3 5

Observations for several consecutive runs:

1. Components are always created in the same order: expected.
2. The order of sequential processing is always the same for both stream and list based flattening algorithms: expected.
3. The order of parallel processing for the list based flattening algorithm varies: expected.
4. The order of parallel processing for the stream based flattening algorithm is almost always the same and only slightly different than those observed for either of the sequential processing results: not expected. I'd think that this should also vary just as (3) does.

The example I used is simplified for brevity, I observed the same behavior in a real application with hundreds of components and actual processing logic (non-empty for each block).

In the real application I time-stamped the peek and implemented a for each block that lasted 1-2 seconds on average to finish but still, there was no overlapping in calls but they always waited for the previous one to finish suggesting that no actual parallel processing happened. I also tried various thread pool sizes between 2 and 2x the number of cores I have but no effect whatsoever.

The only solution that reduced the runtime of the real application to 1/3 and gave me confidence that parallelism was actually used was to switch from stream based flattening algorithm to list based one.

Is my expectation in (4) wrong and if not, what's the explanation for the behavior? Or is the stream based flattening algorithm broken and if yes, what's the fix for it?