Cheap and Secure Web Hosting Provider : See Now

[Solved]: Which all nodes will qualify as an ancestor?

, , No Comments
Problem Detail: 

I was going through the fundamentals of tree structure and the definition for ancestor is as follows:

A node u is an ancestor of v if there is a path from u to v.

enter image description here

Consider the node 11. Is node 2 (not the root, the other one on the left) an ancestor of node 11? It is strictly not a grandparent of 11, however, there does exist a path between these nodes. This is confusing to me, because this would also imply that the sibling nodes (5) of 11 would qualify as an ancestor.

Asked By : Renae Lider

Answered By : David Richerby

The root-2 is an ancestor of 11 (it's the great-grandparent) but you're asking about the 2 on the left, which is not an ancestor. There is no directed path from that node to 11 since the left-2 has no outgoing edges. Paths must respect the direction of the edges. Siblings are not ancestors for the same reason.

(Sometimes, we want to talk about a path that ignores the edge directions. These are usually referred to as something like "paths in the underlying undirected graph".)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44749

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback