Enumerating all binary trees with n nodes.

An interesting problem came up when a colleague asked me to cleanly enumerate all binary trees of n nodes. They can be described as binary strings where 1 represents a non-null node, and 0 represents a null node, then you write out the tree in a pre-order traversal.

Here are some trees and their encodings:

Left to right, top to bottom:

11000  10100
1110000  1101000  1100100  1011000  1010100

It turns out this is related to a whole family of combinatorics problems, and it was easiest to frame it terms of another one: The grid description for monotonic paths that don't cross the diagonal here. The solution is to enumerate all the monotonic paths, but to stop as soon as the diagonal is crossed. It comes out cleanly in haskell:


module BinTreeEnum where

import Data.List
import Data.Monoid

data TStruct = NonEmpty | Empty deriving (Enum, Show)
type TreeDef = [TStruct]

printTStruct :: TStruct -> Char
printTStruct NonEmpty = '1'
printTStruct Empty = '0'

printTreeDef :: TreeDef -> String
printTreeDef = map printTStruct

enumBinTrees :: Int -> [TreeDef]
enumBinTrees n = enumBinTrees' n n where
  enumBinTrees' ups rights | rights < ups = mempty
  enumBinTrees' 0   rights = return (replicate (rights+1) Empty)
  enumBinTrees' ups rights = do
    step <- enumFrom (toEnum 0)
    let suffixes =
          case step of
            NonEmpty -> enumBinTrees' (ups - 1) rights
            Empty -> enumBinTrees' ups (rights - 1)
    suffix <- suffixes
    return (step:suffix)

mainExample = do
  print $ map printTreeDef $ enumBinTrees 4

Here's what you get when you run it:

print $ map printTreeDef $ enumBinTrees 3
["1110000","1101000","1100100","1011000","1010100"]


Which exactly maps to the list of binary trees from above.
It was a fun little problem.