# Is a tree with nodes that have reference to parent still a tree?

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

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. • What makes you doubt it? – user7043 Jan 5 '14 at 1:00
• 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 Jan 6 '14 at 10:13

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.

• +1 for pointing out that having parent links (links in both directions) makes the graph equivalent to an undirected graph. – Giorgio Jan 5 '14 at 9:33
• Can we say any acyclic graph is a tree? – Mohsen Jan 5 '14 at 16:41
• @Mohsen A (directed) acyclic graph that includes a node with two parents is not a tree – Izkata Jan 5 '14 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 Sep 28 '14 at 13:39

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.