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.

Accepted Answer

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.

How to get all possible decision trees with php

Solution

Problem

Related problems