3

Below is a rooted tree, where any node C except root has one parent P

Ancestors of a node C are the nodes on path from C to root, including P,P's parent,P's grandparent, .... till root.

enter image description here

My understanding is, Tree is just a set of nodes & edges that connect these nodes. Between any two nodes there is exactly one single path. A tree does not need to have any root.

Any rooted tree MUST be a tree but any tree may not be a rooted tree.

In the below tree(not a rooted tree),

enter image description here

--

My understanding is, parent-child, depth, height, subtree, siblings, leaf-node concepts are only applied to rooted trees.

If no, then,

Is X a parent of Y? If yes, Who are the ancestors of Y?

Improve this question
3
  • As far as I know your second example is not a tree. In a tree, each node has only one parent, no connection between siblings (no horizontal lines) and 0 or more children. Your second example is a graph.
    – Mandrill
    Sep 15, 2015 at 8:30
  • 1
    Mandrill, the second example is still a tree. A tree is an undirected graph in which there exists exactly one path between any two vertices. Your comments of having a single parent and no connection between siblings do not hold true as the parent ancestor relationship applies only for rooted trees.
    – Shantanu Alshi
    Sep 15, 2015 at 8:40
  • In fact, in some contexts people just speak of "trees" when they mean rooted trees. Therefore, when you read an article by an arbitrary author, make sure you and he means the same.
    – Doc Brown
    Sep 15, 2015 at 19:07

1 Answer 1

Reset to default
4

No. The concept of "parent" and "ancestor" applies to the rooted tree because one unique root is defined and since there is a connected graph there is always a path from any node to the root.

In an unrooted tree there is no root defined and therefore the concepts of "parent" and "ancestor" do not apply.

In that graph either X or Y could be labelled as the root, and if this were the case then either would be parent and ancestor accordingly.

Improve this answer
0

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.