13

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore?

Wikipedia definition is:

In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes.

enter image description here

Improve this question
4
  • 3
    What makes you doubt it?
    – user7043
    Commented Jan 5, 2014 at 1:00
  • 2
    As long as the parent links and the children links are distinct, you can assume that the children links make the tree and the parent links are just an implementation detail.
    – mouviciel
    Commented Jan 6, 2014 at 10:13
  • What brought me here was also pulled Wikipedia page: For example, looking at a tree as a whole, one can talk about "the parent node" of a given node, but in general, as a data structure, a given node only contains the list of its children but does not contain a reference to its parent (if any).
    – andrewlundy_
    Commented Oct 6, 2021 at 15:10
  • By child node reference to the parent node , if that means one node may have multiple parent nodes, it is not a tree. it is a directed graph. In tree, one node may have only one parent at most.
    – Tiina
    Commented May 5, 2023 at 3:43

2 Answers 2

Reset to default
21

A tree is a connected acyclic graph. In the case where we have "parent" links this would just be an undirected tree, but definitely still a tree. If you were to specify that the example is a directed graph it would not be considered a tree (but of course there's no way of telling from the code which was intended).

Some computer science "trees" will include, for instance, links from each node back to the root, or links along each level of a B+ tree. A computer scientist would probably still call these things trees, a mathematician would not.

Improve this answer
4
  • 2
    +1 for pointing out that having parent links (links in both directions) makes the graph equivalent to an undirected graph.
    – Giorgio
    Commented Jan 5, 2014 at 9:33
  • Can we say any acyclic graph is a tree?
    – Mohsen
    Commented Jan 5, 2014 at 16:41
  • 4
    @Mohsen A (directed) acyclic graph that includes a node with two parents is not a tree
    – Izkata
    Commented Jan 5, 2014 at 21:23
  • @Mohsen: You can also define a tree as a graph with a distinct root node such that there exists a unique path from the root to any other node. Clearly, there are acyclic graphs that do not fulfill this definition.
    – Giorgio
    Commented Sep 28, 2014 at 13:39
-2

Let's follow this definition. Will surely get the ans.

A connected graph G is called a tree if the removal of any of its edges makes G disconnected. So, as the graph given above, does not support this statement, so we can not say that the graph given is a tree.

For more info you can continue this link.

http://win.ua.ac.be/~vanhoudt/graph/trees.pdf

Improve this answer
2
  • 1
    You are using the mathematician's point of view here. Note that U2EF1 says in their answer: A computer scientist would probably still call these things trees, a mathematician would not.. Your answer is basically the same as Uiquité's in this respect.
    – Martijn Pieters
    Commented Sep 28, 2014 at 9:11
  • The cited paper assumes undirected graphs. This definition of trees is not appropriate for a directed graph, because (a) it would have to mention that DAGs including trees can at most be weakly connected, and because (b) it allows multiple root nodes. Now notice that the graph in the question is a directed graph (albeit one with backlinks), and that there still is a concept of a root node (hierarchy is denoted by vertical position). A better definition for a directed tree would be: “A (directed) tree is empty or has exactly one root node from which all nodes are reachable”.
    – amon
    Commented Sep 29, 2014 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.