Search code examples
javadata-structurestreeabstract-data-type

ADT Tree - is a node ancestor/descendant of itself?


I'll start saying that there is another question about this on Stack Overflow but I couldn't find a real answer to this because all the answer related to that question were different from each other, and it really confused me more than I already am. My question is this, talking about the Abstract Data Type - Tree (normal not binary tree and in Java programming, just in case it makes difference).

1) is a node of a tree an ancestor/descendant of itself?

Let's say that I looked up for the definition of ancestor and it resulted to be variations of this like:

"a node reachable by repeated proceeding from child to parent"

"a node's ancestor is: itself, its parent, or an ancestor of its parent itself"

"a node U is an ancestor of a node V only if: U = V or U is an ancestor of V's parent"

2) is there a universal definition for "ancestor" or both definitions (including the node itself or not) are right?

3) if the node itself is not considered ancestor of itself, is the definition of a node's depth equal to the number of its ancestors?


Solution

  • You can get inspiration from the axis nomenclature used in the extremely well defined XPath recommendation:

    Given a node in a tree (i.e. the context node), the spec defines axes, i.e. set of nodes relative to the context node:

    • the child axis contains the children of the context node
    • the descendant axis contains the descendants of the context node; a descendant is a child or a child of a child and so on;
    • the parent axis contains the parent of the context node, if there is one
    • the ancestor axis contains the ancestors of the context node; the ancestors of the context node consist of the parent of context node and the parent's parent and so on; thus, the ancestor axis will always include the root node, unless the context node is the root node

    Since it is sometimes useful to operate on descendants or ancestors including the context node, it additionally defines:

    • the descendant-or-self axis contains the context node and the descendants of the context node

    • the ancestor-or-self axis contains the context node and the ancestors of the context node; thus, the ancestor axis will always include the root node

    This model has an answer to your question 1. Other models could differ. Q2: cannot be answered. Q3: simply depends on how depth is defined.