num_trees.rb

# Given a number of keys how many binary search trees can be formed?
def num_trees(n)
  return 1 if n == 0 || n == 1
  (1..n).map do |j|
    num_trees(j - 1) * num_trees(n - j) # left * right (summed)
  end.reduce(:+)
end

p num_trees 0 # should be 1
p num_trees 1 # should be 1
p num_trees 2 # should be 2
p num_trees 3 # should be 5
p num_trees 5 # should be 42