Why No Cycles in Eric Lippert's Immutable Binary Tree?

Question

I was just looking at Eric Lippert's simple implementation of an immutable binary tree, and I have a question about it. After showing the implementation, Eric states that

Note that another nice feature of immutable data structures is that it is impossible to accidentally (or deliberately!) create a tree which contains a cycle.

It seems that this feature of Eric's implementation does not come from the immutability alone, but also from the fact that the tree is built up from the leaves. This naturally prevents a node from having any of its ancestors as children. It seems that if you built the tree in the other direction, you'd introduce the possibility of cycles.

Am I right in my thinking, or does the impossibility of cycles in this case come from the immutability alone? Considering the source, I wonder whether I'm missing something.

EDIT: After thinking it over a bit more, it seems that building up from the leaves might be the only way to create an immutable tree. Am I right?

Answer 1

If you really want to try hard at it you could create a tree with cycles in it that is immutable. For example, you could define an immutable graph class and then say:

Graph g = Graph.Empty
  .AddNode("A")
  .AddNode("B")
  .AddNode("C")
  .AddEdge("A", "B")
  .AddEdge("B", "C")
  .AddEdge("C", "A");

And hey, you've got a "tree" with "cycles" in it - because of course you haven't got a tree in the first place, you've got a directed graph.

But with a data type that actually uses a traditional "left and right sub trees" implementation of a binary tree then there is no way to make a cyclic tree (modulo of course sneaky tricks like using reflection or unsafe code.)