1

I am learning about binary trees. I was given following rules for their creation: A single leaf node is a binary tree. If t1 and t2 are binary trees, then the result of joining them under a single node is a binary tree. I suspect that the tree in the image is not a binary tree. My question is: How can I use the rules to prove that?

Is this a binary tree?

Adam
  • 3,422
  • 1
  • 33
  • 50

2 Answers2

1

Your rule should be amended to require that $t_1$ and $t_2$ are disjoint binary trees, i.e., they have no nodes in common. Then I trust the answer to your question becomes obvious.

Harald Hanche-Olsen
  • 31,960
  • Do I understand it correctly that under current rules, we can't say if it is a binary tree? – Adam Dec 12 '13 at 17:10
  • @Adam: I agree. There has to be a limit of two binary trees being joined to any one node. Otherwise, this is just a tree in general. I think the following would be good enough for binary trees: (1) A single leaf node is a binary tree. (2) If $t_{1}$ and $t_{2}$ are disjoint binary trees, then the resulting tree formed by joining the root node of $t_{2}$ to a node of $t_{1}$ with less than $2$ children is still a binary tree. – Brian Dec 12 '13 at 17:17
0

Trees, by definition, cannot have cycles. This is the reason that your example is not a binary tree. Hanche-Olson's answer is perfectly correct, in that it is a necessary condition to enforce the no-cycles requirement of the definition.

Just realized this would be better placed As a comment in the above answer!

clem
  • 498
  • You say by definition, but is the definition part of the rules I outlined above? If not, then it is not of much use. (Because these rules are supposed to be defining binary trees.) – Adam Dec 12 '13 at 17:46
  • I Think the above rules are meant as rules for generating binary trees, not the actual definition. Any tree cannot have cycles, this is not limited to binary trees. My point is that no tree can be generated by a rule that allows non distinct sub trees. – clem Dec 12 '13 at 17:50
  • Well, the rules are introduced as follows : "Here is a recursive definition of binary trees". – Adam Dec 12 '13 at 18:01
  • Fair enough! They are surely equivalent, given Haralds answer. – clem Dec 12 '13 at 18:59