4

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. Commented Sep 15, 2015 at 8:30
  • 2
    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. Commented 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. Commented Sep 15, 2015 at 19:07

1 Answer 1

Reset to default
5

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.