Tree Terminology: Path

  • Define tree-related terminologies.

Suppose n1,n2,,nkn_1, n_2, \dots, n_k is a sequence of nodes in a tree such that n1n_1 is the parent of n2n_2, which is the parent of n3n_3, and so on, down to nk1n_{k−1}, which is the parent of nkn_k. Then n1,n2,,nkn_1, n_2, \dots, n_k is called a path from n1n_1 to nkn_k.

For example, the sequence 9,17,21,209, 17, 21, 20 is a path from root, 99, to leaf, 2020.

The length of a path is k1k − 1, where kk is the number of nodes on it.

A path may consist of a single node (k=1k = 1), in which case the length of the path is 00.