This

             x
            / \
           /   \
          /     \
         y       None
        / \      / \
       /   \    /   \
    Leaf  Leaf Leaf Leaf

Looks like this.

             x
            / \
           /   \
          /     \
         y       None

There is no reason to explicitly define leafs

But then wouldn’t the right node with None in it be the same as a leaf?

Could you specify what you mean in code maybe? If you don't explicitly define leaves than how can you represent the empty tree?

here, as I said, there is no need to represent an empty tree

https://gist.github.com/MadWombat/798c6d993a7d2ac4ac74d6624a...

So you just throw an error if you try and sort the empty list?

Anyway, I'm pretty sure what you've said here was addressed in the article. The version you've presented here is exactly the first alternative I showed, which isn't as good as a version written with ADTs because you can't represent an empty tree.

Doesn't have to throw an error, could just return an empty list, doesn't matter. All I am saying is that the problem the article describes, where lack of algebraic data types in python makes it impossible to describe the tree structure doesn't exist. There is no need to explicitly represent an empty tree. It is enough to know where your tree ends. Yes, it is more elegant with the ADTs, but it is not impossible without them.

Also, if I really wanted to implement Leaf type, I would probably do it via __new__ and a bit of metaprogramming.