Let $N=\{1,\dots,n\}$. Let $M$ be the set of all binary trees $B$ formed from all elements of $N$ (i.e of size $n$). Let $P$ be a numeric property defined for all $B\in M$. Let $O\in M$ be the optimal $B$ that minimizes $P$.


Example: Let $P$ be the sum of the heights of all nodes of $B$. This measures the "balancing" of $B$, and for $n=2^m-1$ $O$ is even unique.


Task: Given $P$, find (some - ties are OK) $O$.


Attempt 1: Stupid but surefire. Generate all permutations $\Pi$ of $N$. Generate the canonic tree (start empty, insert the elements of $\Pi$ in their order). Compute $P$, pick best $O$.


Attempt 2: If it is possible to derive a simple algorithm that takes a Hamilton walk through the "rotahedron" $G$ of $M$ ($B$ and $B'$ are connected in $G$ if a left rotation move turns $B$ into $B'$) this would at least reduce the load from $n!$ to Catalan($n$). *My question*: Is such an algorithm known?


Note: If $P$ is "very local" such that $G$, turned to a directed graph by pointing the arrow to the smaller $P$, is a DAG, this would speed up things enormously (start anywhere, follow the arrows), but even then, you could end up in a local minimum. ("My" $P$, BTW, would be again the sum of the heights, but dropping the first $k$ elements of $\Pi$.)



Finding the best binary tree with a general property
There are many ways to generate the binary trees systematically. An older example is in [this paper](https://watermark.silverchair.com/290171.pdf%5DADCCAqcGCSqGSIb3DQEHATAeBglghkgBZQMEAS4wEQQMrKjgZkHACgY74gsDAgEQgIICeMZ44ylFTEpgx8fPGdZC0E8nZO4Pmd0nc0uOXM3dRDI03jqH5OdyxRr6xUxItzDL8H88_Dxae1YoAzHc4UynsczKNba1D3k7jk7VGuk293X-4zKk0gYt8RBXF0zo8kDqORhgYlaT5jeROsI0p1RAwxgoSclskVQIxrWQfleFRGbOP5P61HpxD0KzztfGbFks-nn92Ws2xB73dNi8N-gGyJDvHqyYJmTxqLRQixJvvuHnLl6imFlCmHvR5se5ozkoRi7rsrfTKUOdB7FuP1K6Y__8i6KRCucJ1WbFNXm22JsYr2OHH074uyXnoswSF9SG1Pd6Ffsh4VFIQaLsQpHp-FqaQ4lWRaF_ZEyLta74b-C_CTEynpvYfv1C16mU_lOc03IFLcP5UvzdAy65rPihALMDVtnhspuYRMNW2oKbpCNP-sGeQb0TZkpJgfoziOOwoV9ZcGqM-hoI4an0dBTJhFOKVFjwgfg8DpSIJYqu1yGCvvxeKSo4I-Ouiw7r1ZlKMdGZ6XUk8oAN5scfH_Ky2dEC0pG4PhUJzMxjmYSGe6mSR_YhNVc691DMVb_G9akVvLBIgiM1VULPeizNsIxp6yhv9vwzDgyGV3kK2iNXDO0NBZUs_FjY1p-QD35SXPPDoR8tPcT4_YmJdCZUOzUsdkyczmCO6fAVDOI3QAPKKBXzJQLFDXPCN8grdaekEFXScAYIU57-_It_sQdEk3AylucTi6jaf1_NT1_-c_H6UYgcxIJcew9fB5iXge2N_D6L0YIMIhAnGjxetn57nxEWFvuo1KgbYU-TGTOD0Hl8KffPMywYJaJil4Bf6eP6lwAri5H_tEjD5haA).


Another one, perhaps more efficient for your purposes, is [here](https://doi.org/10.1016/0196-6774(90)90030-I).


