Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Consider a tree T containing the set of nodes R
as given by Definition 
.
in a tree T is the length of the unique path in T
from its root r to the node 
.
E.g., the root of T is at level zero and
the roots of the subtrees are of T are at level one. in a tree T
is the length of the longest path from node to a leaf.
Therefore, the leaves are all at height zero. and 
in a tree T.
The node is an ancestor
of the node if there exists a path in T from to .
Notice that and may be the same node.
I.e., a node is its own ancestor.
However, the node
is a proper ancestor
if there exists a path p in T from to
such that the length of the path p is non-zero. is a descendant
of the node if there exists a path in T from to .
And since and may be the same node,
a node is its own descendant.
The node
is a proper descendant
if there exists a path p in T from to
such that the length of the path p is non-zero.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.