Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx[This is part of a series on generating every string in a language. The previous part is here . The next part is here .] Last time we talked about how the number of binary trees with n nodes is C(n), where C(n) is the nth Catalan number. I asked if thereen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10007833Wed, 05 May 2010 15:43:31 GMT91d46819-8472-40ad-a661-2c78acb4018c:10007833jsrfc58<p>Oops...I meant to write "ternary tree" not "tertiary tree". And...a four-node tree would be a quadtree, etc.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10007833" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10007825Wed, 05 May 2010 15:33:07 GMT91d46819-8472-40ad-a661-2c78acb4018c:10007825jsrfc58<p>Eric wrote: "Binary trees have more structure than arbitrary trees! There are two binary trees with two nodes: one with the child on the right of the root, one with the child on the left of the root. There is only one arbitrary tree with two nodes; there is no difference between the "left" and "right" child."</p>
<p>I think this argument depends on what function you are using to generate new nodes in the tree.</p>
<p>For example, if you have a binary tree, and you are adding a new value, you could create a new node on the left if the incoming value is less than the current node value. That rule is arbitrary, however, because you could reverse that and instead create a new node on the right. Now does that constitute one binary tree, or two?</p>
<p>Also, with arbitrary trees, it depends on how you define them. To say there is no difference between the left and the right child really depends on what type of arbitrary tree you are describing. If you have some type of function which determines how new nodes are created, they may in fact have more structure than a binary tree.</p>
<p>For instance, if an incoming value is compared to an existing node, you could have it create a left node if the value is less, a right node if the value is greater, and a middle node if the value is equal. (would that make it a tertiary tree?) </p>
<p>Anyway, you could scale this "gateway" function so that four, five, or six (or more) nodes are created. I would argue that a six-node tree would have more structure than a binary tree in this case. I haven't done the math on it, but would it possibly have 6! different configurations?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10007825" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10002768Mon, 26 Apr 2010 20:48:19 GMT91d46819-8472-40ad-a661-2c78acb4018c:10002768hp<p>Generating all possible pictures:</p>
<p><a rel="nofollow" target="_new" href="http://aboutintelligence.blogspot.com/2008/05/generating-all-possible-pictures.html">http://aboutintelligence.blogspot.com/2008/05/generating-all-possible-pictures.html</a></p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10002768" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001843Sat, 24 Apr 2010 02:22:00 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001843Pop Catalin<p>It's interesting that for binary trees the following are considered distinct configurations</p>
<p> A A</p>
<p> \ \</p>
<p> B B</p>
<p> / \</p>
<p> C C</p>
<p>but if they are viewed as general trees they are not distinct, it's the same configuration. </p>
<p>There's a distinction in the definitions given for the binary and arbitrary trees, the binary tree definition contains node position information (which also implies ordering), but the definition of general trees only contains ordering information. (without position information)</p>
<p>If we were to define the the binary trees without any position information, something like : a binary tree is a tree where every node has a maximum of two child nodes (maybe as a linked list) then the number of possible configurations is reduced by a large factor. (Intuitively I think 2n!, but I need to verify)</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001843" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001818Sat, 24 Apr 2010 00:53:02 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001818Mark Knell<p>> No, that is exactly the opposite of what I need. If A is {} and B is {{}} then I want {{}{{}}} and {{{}}{}} to be different trees. An ordered list gives me exactly the ordering I need.</p>
<p>My version does distinguish {{}{{}}} from {{{}}{}}, fwiw, so I don't think it's the opposite of what you need. It would produce the exact results you require. </p>
<p>But, it is unnecessarily complex. I think I've both introduced a wrinkle and compensated for it, when I should have let well enough alone.</p>
<p>Consider two graphs: </p>
<p> A</p>
<p>/ | \ </p>
<p>B C D</p>
<p>|</p>
<p>E</p>
<p>And</p>
<p> A</p>
<p>/ | \ </p>
<p>B D C</p>
<p>|</p>
<p>E</p>
<p>I thought a plausible reading of your original definition would say that in the first case, A's list of children is {B, C, D}, in the second it is {B, D, C}. These are different lists, but you wish them to describe the same tree. </p>
<p>However, this confers more differentiable identity to the nodes than I should. You've shown trees with labels, but the labels have been based on positions, i.e., labeled after order is fixed. My instinct is to quibble with this, saying, "Yeah, but what if we reverse the order in which we visit the leafs under A; it's the same 'shape' but with different 'order'." Upon reflection, I think that's begging the question. It already assumes that node identity is meaningful apart from position. That's something I cooked up; you don't distinguish nodes in any way other than their subtrees and their order relative to their siblings. It's reminiscent of the story about the three baseball umpires (which you've featured). To paraphrase the oldest umpire, your nodes ain't nothing until you've ordered them. </p>
<p>I've probably spent too much time serializing things lately.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001818" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001793Fri, 23 Apr 2010 22:44:52 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001793Mark Knell<P>> Let's say that an arbitrary tree is defined as either (1) the empty arbitrary tree, or (2) a list (possibly empty) of *non-empty* arbitrary trees called the children. </P>
<P>If you're using the same notion of ordering as you did last post, you probably want a bit more detail on how the children are ordered. Maybe something like: If two permutations of the children only transpose children that have similar subtrees, the permutations are considered equivalent. </P>
<P>In other words, if "list" entails being well ordered, then that's too strict an ordering for your needs. You need a collection that allows a root with children {A, B} to be equated with a root with children {B, A}.</P>
<DIV class=yellowbox>
<P>No, that is exactly the opposite of what I need. If A is {} and B is {{}} then I want {{}{{}}} and {{{}}{}} to be different trees. An ordered list gives me exactly the ordering I need.</P>
<P>With these definitions it becomes plausible that binary trees and arbitrary trees are isomorphic, since both of them are <EM>recursively defined collections of pairs</EM>. A binary tree is a collection of left/right pairs, and an arbitrary tree is a collection of head/tail pairs.</P></DIV><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001793" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001781Fri, 23 Apr 2010 21:51:47 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001781John Kallen<P>"Next time: what else can we generate all of?"</P>
<P>Eric: how about generalizing from binary trees to arbitrary directed graphs (including cycles). That way you could generate what amounts to control flow graphs of basic blocks. You might think of it as useful for generating control flow graphs for the testing of the back end of a compiler (or decompiler, in my case). However, the number of graphs is likely to grow very fast with the number of nodes. And attempting to filter out the many isomorphic graphs doesn't work as graph isomorphism is hard (not P, but apparently not NP-complete either).</P>
<DIV class=yellowbox>
<P>Interesting idea. You're right, it's the isomorphic graphs that are hard to identify. Simply generating all the directed graphs with n nodes is easy; there are 2^(n^2) of them. Imagine an n by n matrix of Booleans that says whether there is an edge from x to y; there is one graph for every possible combination of Booleans in that matrix. Easily enumerated: just make an n x n bit integer and count from zero until you're done. -- Eric </P></DIV><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001781" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001711Fri, 23 Apr 2010 19:39:10 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001711Philip<p>Just a note of pedantry;</p>
<p>If there are two trees of size 2 (binary), A in root with B left, A in root with B right...</p>
<p>The you could also say that there are four for a structured tree of size 4: A in root with B in child position 0 (nodes 1-3 empty), ... A in root with B in child position 3 (nodes 0-2 empty).</p>
<p>When reading your question, it was not clear to me if "any arbitrary tree" meant "a tree with an arbitrary structure" or "any structured tree picked arbitrarily". So I answered "it depends" :)</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001711" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001653Fri, 23 Apr 2010 17:56:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001653Mark Knell<p>> It's amazing how many people get hopelessly tangled up</p>
<p>This is completely off Eric's topic, but it's interesting to me how common this view of technical difficulty is. Namely, that a problem that's only mildly complex in general should still only be mildly complex to solve in an interview. I used to think that, too.</p>
<p>Over the years, though, I've had a couple of interviews where I drew blanks on (or got "hopelessly tangled up" in) things I not only should have known, but did know cold in my everyday routine. And certainly I've been on the interviewing side of of plenty of trainwreck responses to even trivial problems, such as "in the language of your choice, write code to traverse a binary tree". The Coding Horror blog has recurring posts about even simpler sorts of problems causing difficult. </p>
<p>Two things changed my mind. One, I've heard that the most widely-held fear in the US is public speaking--outranking spiders, needles, planes, internet outtages, etc. For many, relatedly I think, the interview is NOT a representative sample of their technical skill. </p>
<p>And two, consider the last time you made an important technical presentation (say, to a client or a boss). Did you choose to do it without having prepared or rehearsed? If you rehearsed, why? For many, we rehearse because thinking things through in advance, where you can be meticulous at your own speed, is different from trying to produce meticulous results rapidly, for an audience. And that's when you know what the questions are likely to be in advance!</p>
<p>I'm not saying this sort of question is an unfair test of a candidate, or that speaking and thinking on your feet is not an important skill, even for a "heads down" developer. But I do think that most interviewers underestimate how technical degree-of-difficulty amplifies when introduced in an interview. They think it says something about the population, and maybe it does--but I think a significance fraction of the result can be explained by sheer anxiety.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001653" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001591Fri, 23 Apr 2010 16:10:18 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001591Tony Cox [MSFT]<p>On the theme of "generating all of...": printing all anagrams of a given input word is a question I sometimes pose to candidates in interviews. It's amazing how many people get hopelessly tangled up by it.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001591" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001434Fri, 23 Apr 2010 11:23:39 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001434Random832<p>A bit of an irrelevant question:</p>
<p>This algorithm places the string representations, at least for the 4/5 case, very nearly in reversed lexical order (with one item two positions out of place) - and where they are out of place it is in the same way for both of them.</p>
<p>So my question is: Do these string representations always guarantee that the binary tree and the arbitrary tree's string representation will be in the same place in their respective lexical order* And is there an algorithm that will always generate them in lexical order (other than the obvious case of generating the string representations via a 'what characters are valid in the next position' method and trying them in lexical order)</p>
<p>*assuming { comes before }, and that ( comes before ) which both come before x.</p>
<p>Interesting fact 2: the arbitrary tree representation can be obtained from the binary tree representation by removing all )'s and changing (x to {}</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001434" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001379Fri, 23 Apr 2010 08:06:28 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001379Szindbad<P>"Next time: what else can we generate all of?"</P>
<P>Maybe sentences/syntax trees of a context free language? :)</P>
<DIV class=yellowbox>
<P>Maybe! -- Eric</P></DIV><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001379" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001370Fri, 23 Apr 2010 07:41:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001370francis d<P>So, arbitrary trees can't have null child nodes? Their child nodes can't be right, left or somewhere in the middle? I thought in order to generate arbitrary trees, I would need to know the maximum number of child nodes for each node. I understand the explanation in wikipedia for "Encoding general trees as binary trees" but I'm just looking at the tree as a bunch of dots and lines.</P>
<P>So what makes an arbitrary tree an arbitrary tree and not some other kind of tree?</P>
<DIV class=yellowbox>
<P>Good questions. Let's make some formal definitions. </P>
<P>Let's say that a list of things is recursively defined as (1) the empty list of things, or (2) a pair: a thing called the head, and a list of things called the tail.</P>
<P>Let's say that a binary tree is recursively defined as (1) the empty binary tree, or (2) a pair: a binary tree called left, and a binary tree called right. </P>
<P>Let's say that an arbitrary tree is defined as either (1) the empty arbitrary tree, or (2) a list (possibly empty) of *non-empty* arbitrary trees called the children. </P>
<P>Does that answer your question? -- Eric</P></DIV><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001370" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001356Fri, 23 Apr 2010 07:15:11 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001356David Moles<p>"Next time: what else can we generate all of?"</p>
<p>Arbitrary trees with ordered nodes?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001356" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001305Fri, 23 Apr 2010 05:31:29 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001305Bahador<p>This brilliant way of seeing the solution was really humbling for me. I couldn't see this elegant solution myself if my life depended on it ;)</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001305" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001188Fri, 23 Apr 2010 00:24:49 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001188Adam Robinson<p>I think the idea of "since binary trees are a special case of arbitrary trees, then there must be more arbitrary trees" is including the binary trees *in* the list of arbitrary trees. In other words, if all binary trees are trees--and there are trees that are not binary trees--then there are more (general) trees than binary trees.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001188" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001034Thu, 22 Apr 2010 19:58:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001034Chris B<p>I think this could easily be extended to generate binary expressions (binary trees), and probably for variadic expressions (arbitrary trees) as well. This would of course be a handy tool to test portions of a compiler...</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001034" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001021Thu, 22 Apr 2010 19:36:56 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001021DRBlaise<p>Thanks for the interesting post as usual. Below is my version of converting Binary Tree to Arbitrary Tree:</p>
<p>static TreeNode BinaryTreeToTree(Node binary)</p>
<p>{</p>
<p> return new TreeNode(BinaryNodeToTreeChildren(binary));</p>
<p>}</p>
<p>static IEnumerable<TreeNode> BinaryNodeToTreeChildren(Node binary)</p>
<p>{</p>
<p> for (Node right = binary; right != null; right = right.Right)</p>
<p> yield return BinaryTreeToTree(right.Left);</p>
<p>}</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001021" width="1" height="1">re: Every Tree There Ishttp://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx#10001005Thu, 22 Apr 2010 19:07:49 GMT91d46819-8472-40ad-a661-2c78acb4018c:10001005LB20789<p>I think an interesting variation on this topic (and the last one) would be to modify the algorithm to generate all "structurally" unique trees - excluding those that contain reflections of nodes within the structure. There are *far fewer* unique trees than binary trees. For example, for N=32, there are 55,534,064,877,048,198 binary trees but only 18,632,325,319 unique binary trees. FInding a way to produce unique trees in a streaming manner (not storing prior state) would be an interesting challenge ... and I'm not even sure it's possible.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10001005" width="1" height="1">