Can a Node Have Multiple Parents in Trees?

AI Thread Summary
In tree data structures, a node cannot have more than one parent, as this would create cycles, which are not allowed in trees. The discussion highlights that while unrooted trees exist in graph theory, they do not conform to the traditional parent-child hierarchy found in rooted trees. For modeling complex relationships, such as in phylogenetic studies, phylogenetic networks are suggested as they can accommodate multiple relationships, unlike trees. The concept of multiple inheritance in object-oriented programming is mentioned as an analogy, illustrating that once multiple parentage is introduced, the structure ceases to be a tree. Understanding these distinctions is crucial for accurately representing relationships in data structures and biological models.
mohamed el teir
Messages
88
Reaction score
1
i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??
 
Technology news on Phys.org
What circumstances would you use such a data structure? Sounds like a relational database.
 
newjerseyrunner said:
What circumstances would you use such a data structure? Sounds like a relational database.
i am not planning now to use this but as a concept i want to know is this right or wrong
 
mohamed el teir said:
[...]
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??

That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).
 
Last edited:
Dominik Tugend said:
That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).
so what does an unrooted tree exactly mean ?
 
  • Like
Likes jim mcnamara
In graph terminology, any graph without cycles is a tree. As a data structure, the navigability between nodes, like parent and child relations, usually express some kind of hierarchy between nodes which comes "on top" of the tree graph in order to serve some purpose, like for instance expressing a search tree. In principle you could have tree data structures with many or no roots depending on what the relationship means.
 
Usually the point of a tree is to know where you came from, which implies a single parent. If you're just wanting to conserve space, you could wrap all of your nodes in a reference counter.
 
Supposing your current concern is about computational molecular biology, particularly algorithmic approaches available to building phylogenetic trees.
mohamed el teir said:
i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).
Yes, that is partly true about the inadequacy of using phylogenetic trees alone to represent the histories of species in question. As a matter of fact, two daughter branches may have only one parent in a binary tree.
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??
There are actually several types of trees used to model species relationships in phylogenetic study. The most commonly mentioned ones are rooted and unrooted trees, either of which can't be used to fully model outcomes of such events of the so-called reticulate evolution as gene transfer, hybridization, recombination, reassortment etc. These are what your concern is exactly about that whether or not a child can have two parents at the same time. We therefore have to opt to choose a better modeling tool called a phylogenetic network instead, which is also a graph being again as either rooted (e.g split, median, quasi-median, etc.) or unrooted (e.g haplotype, reticulograms) one. You can google on these terms to learn more about their applications in practice.
 
  • #10
I seem to recall that C++ allows multiple inheritance, which may be an example of what you are referring to. For example, a given object O can inherit properties from two different ancestors. It can also be the parent of multiple descendants. For a designer point of view, this turned out to be a prescription for disaster, which is why most OO languages do NOT support multiple inheritance. So we're not talking trees, per se, but once you start doing that, you no longer have a tree, as was pointed out above. You just have a graph. And you can try to avoid cycles in it, but it's not what is called a "tree" any longer in strict comp. sci. terminology.
 
Back
Top