448,733 Members | 1,636 Online
Need help? Post your question and get tips & solutions from a community of 448,733 IT Pros & Developers. It's quick & easy.

Empty binary trees

 P: n/a Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left' and 'Right' subtrees of the original tree." My Questions: 1) Why they talk about a binary tree that is totally empty? I mean a binary tree with Zero elements? 2) A binary tree is partioned into three disjoint subsets. That means all the elements in a binary tree should be unique? Duplicate elements are allowed within a subtree? Any significance of this? Thanks, Vinodh Jun 27 '08 #1
7 Replies

 P: n/a Vinodh wrote: Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left' and 'Right' subtrees of the original tree." My Questions: 1) Why they talk about a binary tree that is totally empty? I mean a binary tree with Zero elements? It's needed in the recursive definition. If you do not allow subtrees to be empty, then your trees cannot have leaves and will be infinite. 2) A binary tree is partioned into three disjoint subsets. That means all the elements in a binary tree should be unique? Yes. Duplicate elements are allowed within a subtree? No. Any significance of this? Yes: trees do not have cycles. BTW: your question is basically unrelated to C++ and would be better suited for comp.programming. Best Kai-Uwe Bux Jun 27 '08 #2

 P: n/a Kai-Uwe Bux wrote: >2) A binary tree is partioned into three disjoint subsets. That meansall the elements in a binary tree should be unique? Yes. >Duplicate elements are allowed within a subtree? No. That would be incorrect. You are confusing binary trees with binary search trees. A binary tree doesn't impose any limitations whatsoever on the contents of the nodes. It only defines the structure of the tree (each node can have one parent node and two subtrees). What you are thinking about is a binary search tree, which has the additional limitation that all the nodes in the left subtree must be smaller than the node itself, and the ones on the right subtree larger. Jun 27 '08 #3

 P: n/a Juha Nieminen wrote: Kai-Uwe Bux wrote: >>2) A binary tree is partioned into three disjoint subsets. That meansall the elements in a binary tree should be unique? Yes. >>Duplicate elements are allowed within a subtree? No. That would be incorrect. You are confusing binary trees with binary search trees. I don't think that I am confusing anything here. A binary tree doesn't impose any limitations whatsoever on the contents of the nodes. We have to distinguish the dublication of labels from the dublication of nodes. In a tree, subtrees will not share nodes. However, different nodes might share labels. The definition that the OP refers to is clearly not talking about labels but about nodes. It only defines the structure of the tree (each node can have one parent node and two subtrees). And those subtrees do not share nodes. What you are thinking about is a binary search tree, which has the additional limitation that all the nodes in the left subtree must be smaller than the node itself, and the ones on the right subtree larger. You are blurring the distinction of nodes and labels. That is not a good idea when talking about trees. The comparison applies to labels. The requirement that nodes be distinct is just a consequence of the absence of cycles in trees. Best Kai-Uwe Bux Jun 27 '08 #4

 P: n/a On Jun 3, 7:50*pm, Kai-Uwe Bux 2) A binary tree is partioned into three disjoint subsets. That meansall the elements in a binary tree should be unique? Yes. >Duplicate elements are allowed within a subtree? No. * That would be incorrect. You are confusing binary trees with binary search trees. I don't think that I am confusing anything here. * A binary tree doesn't impose any limitations whatsoever on the contents of the nodes. We have to distinguish the dublication of labels from the dublication of nodes. In a tree, subtrees will not share nodes. However, different nodes might share labels. The definition that the OP refers to is clearly not talking about labels but about nodes. It only defines the structure of the tree (each node can have one parent node and two subtrees). And those subtrees do not share nodes. Right.I was talking about nodes only. And I was not asking about "Binary Search Tree" which seems to be a specialization of a Binary Tree. The statement that subtrees do not share nodes in a binary tree is in synch with the definition of "the subtrees are disjoint". Thanks for validating my understanding. * What you are thinking about is a binary search tree, *which has the additional limitation that all the nodes in the left subtree must be smaller than the node itself, and the ones on the right subtree larger. You are blurring the distinction of nodes and labels. That is not a good idea when talking about trees. The comparison applies to labels. The requirement that nodes be distinct is just a consequence of the absence of cycles in trees. >Duplicate elements are allowed within a subtree? No. Right. Recursively if we check I find that, since root and subtrees can not have anything common, between root, left and right nothing is going to be common in a binary tree. Hence now I am able to understand every node value in a binary tree is Unique. Thanks Thouh I don't know the significance of this Uniqueness.:( Best Kai-Uwe Bux Jun 27 '08 #5

 P: n/a On Jun 3, 10:18*pm, Vinodh >2) A binary tree is partioned into three disjoint subsets. That means >>all the elements in a binary tree should be unique? >Yes. >>Duplicate elements are allowed within a subtree? >No. * That would be incorrect. You are confusing binary trees with binary search trees. I don't think that I am confusing anything here. * A binary tree doesn't impose any limitations whatsoever on the contents of the nodes. We have to distinguish the dublication of labels from the dublication of nodes. In a tree, subtrees will not share nodes. However, different nodes might share labels. The definition that the OP refers to is clearly not talking about labelsbut about nodes. It only defines the structure of the tree (each node can have one parent node and two subtrees). And those subtrees do not share nodes. Right.I was talking about nodes only. And I was not asking about "Binary Search Tree" which seems to be a specialization of a Binary Tree. The statement that subtrees do not share nodes in a binary tree is in synch with the definition of "the subtrees are disjoint". Thanks for validating my understanding. * What you are thinking about is a binary search tree, *which has the additional limitation that all the nodes in the left subtree must be smaller than the node itself, and the ones on the right subtree larger.. You are blurring the distinction of nodes and labels. That is not a good idea when talking about trees. The comparison applies to labels. The requirement that nodes be distinct is just a consequence of the absence of cycles in trees. Duplicate elements are allowed within a subtree? No. Right. Recursively if we check I find that, since root and subtrees can not have anything common, between root, left and right nothing is going to be common in a binary tree. Hence now I am able to understand every node value in a binary tree is Unique. Thanks Thouh I don't know the significance of this Uniqueness.:( Best Kai-Uwe Bux- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text - Okay....Okay....Now I got it. It is that nodes or lables are distinct. But the data storage I mean the values we store may be anything which means that we may have redundant data in a tree.Interesting.... Jun 27 '08 #6

 P: n/a Kai-Uwe Bux wrote: We have to distinguish the dublication of labels from the dublication of nodes. In a tree, subtrees will not share nodes. However, different nodes might share labels. I understood "no duplicate elements" to mean that the same value cannot be stored in the tree twice. I apologize for the misunderstanding. Jun 27 '08 #7

 P: n/a On Jun 3, 2:06 pm, Kai-Uwe Bux