How do I iterate over binary trees? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:16:13Z http://mathoverflow.net/feeds/question/3653 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees How do I iterate over binary trees? Kim Greene 2009-11-01T09:29:02Z 2012-04-05T19:58:02Z <p>Suppose I have n-1 distinguishable labels for internal nodes A={a1, a2, ..., an-1} and n distinguishable labels for leaves B={b1,b2, ..., bn} with A and B disjoint. What is the best way to iterate over all possible binary trees if I label without replacement?</p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/3659#3659 Answer by Dan Petersen for How do I iterate over binary trees? Dan Petersen 2009-11-01T12:00:21Z 2009-11-01T12:00:21Z <p>Disclaimer: I have no computer science background, this is probably not the fastest method of solving your problem.</p> <p>It is easy to iterate over all unlabeled binary trees of a given size. (I hope you agree.)</p> <p>If what you're doing is computing some sum over binary trees, then the easiest way to reduce to this situation might be to first iterate over all unlabeled trees, and then for each unlabeled tree add</p> <p>1/|Aut(T)|&#042;(sum over all (n-1)!&#042;n! possible labelings of the tree T)</p> <p>where Aut(T) is the group of automorphisms of the tree. The cardinality of the automorphism group can be computed recursively: one defines a function (in pseudocode)</p> <pre><code>function Aut(T): if T == {leaf}: return 1 T1, T2 &lt;- T.subtree(left), T.subtree(right) if T1==T2: return 2*Aut(T1)^2 else: return Aut(T1)*Aut(T2) </code></pre> <p>When you compare whether T1 and T2 are equal, you can again use recursion.</p> <pre><code>function equals(T1,T2): if T1 == {leaf}: return T2 == {leaf} if T2 == {leaf}: return false T11,T12,T21,T22 &lt;- T1.subtree(left), T1.subtree(right), T2.subtree(left), T2.subtree(right) if equals(T11,T21): return equals(T12,T22) if equals(T11,T22): return equals(T11,T22) return false </code></pre> <p>If you're not computing a sum but you really want an iterator over all labeled trees, one way could be to implement something similar to this. First iterate over all unlabeled trees, then for each internal vertex of your tree check whether there exists an automorphism switching the left and right subtree. If so, rigidify the tree by imposing the condition that the root at the left subtree should be labeled by a smaller element than the root at the right subtree; sum only over these labelings.</p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/3696#3696 Answer by Darsh Ranjan for How do I iterate over binary trees? Darsh Ranjan 2009-11-01T19:30:33Z 2009-11-01T19:30:33Z <p>This seems naturally recursive. For each choice of root and each subset of the internal nodes, you have to generate all possible left subtrees using those internal nodes, and all possible right subtrees using the remaining nodes. For each pair of those, you have to generate all permutations of the leaves. </p> <p>That's if the left and right branches are considered distinguishable, so if "r(L, R)" means the binary tree with root r, left subtree L, and right subtree R, then r(L, R) and r(R, L) are not the same. On the other hand, if the relation "r(L, R) = r(R, L)" holds, then you can avoid double-counting in the following way: for each choice of root, pair each subset S of the remaining internal nodes with its complement S<sup>c</sup>, and out of each pair, pick <i>one</i> to use as the nodes for the left subtree; don't use both it and its complement. You still generate all permutations of the leaves for each pair of left and right subtree. </p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/3702#3702 Answer by Jonah Ostroff for How do I iterate over binary trees? Jonah Ostroff 2009-11-01T20:09:20Z 2009-11-01T20:24:30Z <p>Wait, you mean n+1 labels for the leaves and n labels for the internal nodes, right?</p> <p>Note that such trees are counted by the multinomial coefficient {2n choose 2,2,2,2,...,2} (with n 2s), because their <a href="http://en.wikipedia.org/wiki/Prufer_sequence" rel="nofollow">Prüfer codes</a> are exactly the ones containing 2 of all but one of the b<sub>i</sub>s and 1 of the last one. If you take such a Prüfer code and affix to its end the label of the root, then you're just counting anagrams of b<sub>1</sub>b<sub>1</sub>b<sub>2</sub>b<sub>2</sub>...b<sub>n-1</sub>b<sub>n-1</sub>b<sub>n</sub>b<sub>n</sub>. I'm not a computer scientist, but these are easy enough to loop through, right?</p> <p>EDIT: Wait, sorry, this counts full binary trees where left and right children are indistinguishable. I suppose this isn't what you want, is it?</p> <p>Not too hard to fix, fortunately, since the nodes are already labeled: just decide for each internal node whether the child with the higher label is on the right or left. There are 2<sup>n</sup> ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b<sub>1</sub>c<sub>1</sub>b<sub>2</sub>c<sub>2</sub>...b<sub>n-1</sub>c<sub>n-1</sub>b<sub>n</sub>c<sub>n</sub>. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:</p> <p>First, chop off the last letter, treat the c<sub>i</sub>s as b<sub>i</sub>s, and find the tree with this new string as its Prüfer code. Choose the letter you chopped off to be the root, so every internal node now has two children. To decide which is on the left and which is on the right, ask whether b<sub>i</sub> came before c<sub>i</sub> in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.</p> http://mathoverflow.net/questions/3653/how-do-i-iterate-over-binary-trees/93249#93249 Answer by Victor Miller for How do I iterate over binary trees? Victor Miller 2012-04-05T19:58:02Z 2012-04-05T19:58:02Z <p>The paper "Binary Tree Gray Codes" by Proskurowski and Ruskey, in the Journal of Algorithms <a href="http://dx.doi.org/10.1016/0196-6774(85)90040-9" rel="nofollow">http://dx.doi.org/10.1016/0196-6774(85)90040-9</a> gives a method of generating all binary trees, so that the successive in the generation differ by a constant amount. It also gives references to previous such algorithms.</p>