Is a node in a tree considered its own ancestor?

Question

I'm wondering what the consensus is on the definition of "ancestor" in a computer science context.

I only ask because in Introduction to Algorithms, Second Edition, p. 259 there is a description of the algorithm Tree-Successor(x) that seems odd. In finding the successor of node x,

[...] if the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.

In a binary search tree with a root having key 2 and children 1 and 3, the successor of 1 is its parent 2. In this case, x is the left child of x's successor, y. According to the book's definition, then, x must be its own ancestor, unless I'm missing something.

I haven't found anything in the errata about this.

Answer 1

Is a node in a tree considered its own ancestor?

Not normally, AFAIK. For example, in the Wikipedia page on binary trees, ancestor is defined thus:

If a path exists from node p to node q, where node p is closer to the root node than q, then p is an ancestor of q and q is a descendant of p.

But apparently that text book's definition of ancestor is such that a node is its own ancestor. This definition is not exactly intuitive, but a textbook is free to introduce its own definitions for the terminology that it uses. Maybe this definition simplifies some of the related descriptions / theorems / etc.

Answer 2

No, a node is not ancestor of itself. According to me it should be: if the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is either x or an ancestor of x. but the code given in the book supposedly handling such type of cases.

Answer 3

It's merely a matter of definition, but in this case, yes. CLRS define an ancestor of x as any node on the unique path from the root to x, which by definition includes x.

The sentence fragment you quoted begins by mentioning exercise 12.2-6 on the next page, which specifies this:

(Recall that every node is its own ancestor.)

:-)