Sample traversal through the space of binary trees

Setup (RUN ME FIRST)

!pip install git+https://github.com/tdene/synth_opt_adders.git@v1.0.1

Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/
Collecting git+https://github.com/tdene/synth_opt_adders.git@v1.0.1
  Cloning https://github.com/tdene/synth_opt_adders.git (to revision v1.0.1) to /tmp/pip-req-build-k8o5hiql
  Running command git clone -q https://github.com/tdene/synth_opt_adders.git /tmp/pip-req-build-k8o5hiql
Requirement already satisfied: networkx in /usr/local/lib/python3.7/dist-packages (from pptrees==1.0.1) (2.6.3)
Requirement already satisfied: pydot in /usr/local/lib/python3.7/dist-packages (from pptrees==1.0.1) (1.3.0)
Requirement already satisfied: graphviz in /usr/local/lib/python3.7/dist-packages (from pptrees==1.0.1) (0.10.1)
Requirement already satisfied: Pillow in /usr/local/lib/python3.7/dist-packages (from pptrees==1.0.1) (7.1.2)
Requirement already satisfied: pyparsing>=2.1.4 in /usr/local/lib/python3.7/dist-packages (from pydot->pptrees==1.0.1) (3.0.9)
Building wheels for collected packages: pptrees
  Building wheel for pptrees (setup.py) ... done
  Created wheel for pptrees: filename=pptrees-1.0.1-py3-none-any.whl size=61063 sha256=f548515389e0bfc49efc912a0b7a16dab903d18b5fe29c101e3cf21aa67dbc12
  Stored in directory: /tmp/pip-ephem-wheel-cache-hgz9h89m/wheels/2b/71/d4/23b31fc1138125ab78a2940e8bfad3f80cf5c59401e40c24ce
Successfully built pptrees
Installing collected packages: pptrees
Successfully installed pptrees-1.0.1

Create and visualize trees

Specify the number of desired leafs in the tree.

If a different width is desired, simply change these parameters and presss CTRL+F9 (or go to the taskbar, Runtime -> Run All). No other modifications are required.

width = 6

Create all binary trees with the specified number of leafs

from pptrees.AdderTree import AdderTree as tree
from pptrees.util import catalan as catalan

cn = catalan(width-1)
ary = []
for a in range(cn):
  t = tree(width, start_point = a)
  ary.append(t)

Display the result as a GIF

Note that this GIF composition can take a very long time. Generating all trees is fast, but composing them into a GIF is not.

from pptrees.util import display_gif as display_gif
from IPython.display import Image

Image(display_gif(ary))