How to get all possible decision trees with php

Question

I'm looking to build all possible decision trees with php. What I'm looking for is exactly like this answer, however, I need it in php, and I'm having difficulty interpreting the LINQ; and the stringbuilder probably needs to be an array.

Answer 1

Here's a PHP version that returns a collection of trees formed from arrays.

function AllBinaryTrees($size = 0)
{
  // empty tree, size=0
  if ($size === 0) { return array(null); }

  // otherwise take 1 from the size for the root of the current subtree and
  // split the rest over the subtrees in every possible way
  $trees = array();
  $size --;

  for ($leftsize=0; $leftsize <= $size; $leftsize ++)
  {
     foreach(AllBinaryTrees($leftsize) as $left)
       foreach(AllBinaryTrees($size-$leftsize) as $right)
       {
          // add the new tree to the collection
          $trees[] = array('left' => $left, 'right' => $right);
       }
  }
  return $trees;
}

Note that this is not the most efficient way to do it, because we generate subtrees of a given size again and again, so caching them would be better. We could wrap this function in a class that keeps a cache with trees for every size.

Answer 2

This is the algorithm with memoization:

function AllBinaryTrees($size)
{
    static $cache = [];

    if ($size <= 0) {
        return [null];
    }

    if (isset($cache[$size])) {
        return $cache[$size];
    }

    $trees = [];

    foreach (range(0, $size - 1) as $i) {
       foreach (AllBinaryTrees($i) as $left) {
           foreach(AllBinaryTrees($size - 1 - $i) as $right) {
               $trees[] = ['left' => $left, 'right' => $right];
           }
       }
    }

    return $cache[$size] = $trees;
}