rooted tree

let $\text{[math]}$ be a finite set. a rootedd tree on $\text{[math]}$ is defined by the pair $\text{[math]}$ where $\text{[math]}$ is a function $\text{[math]}$ such that

there is no positive integer $\text{[math]}$ such that $\text{[math]}$ for some element $\text{[math]}$ , and
there is exactly one element $\text{[math]}$ such that $\text{[math]}$ , called the root.

[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]

for each nonroot node $\text{[math]}$ , $\text{[math]}$ is called the parent of $\text{[math]}$ in the tree, and the ordered pair $\text{[math]}$ is called the parent arc of $\text{[math]}$ in the tree. an arc of the tree is the parent arc of some nonroot node. if the parent of $\text{[math]}$ is $\text{[math]}$ then $\text{[math]}$ is a child of $\text{[math]}$ and $\text{[math]}$ is the child arc of $\text{[math]}$ .
[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]

a rooted tree has arity $\text{[math]}$ if every node has at msot $\text{[math]}$ children. a binary tree is a tree that has arity 2.
[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]

we say two nodes are adjacent if one is the parent of the other. we say the arc $\text{[math]}$ is incident to the nodes $\text{[math]}$ and $\text{[math]}$ .
[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]

the ancestors of $\text{[math]}$ are defined inductively: $\text{[math]}$ is its own ancestor, and (if $\text{[math]}$ is not the root) the ancestor's of $\text{[math]}$ 's parent are also ancestors of $\text{[math]}$ . if $\text{[math]}$ is the ancestor of $\text{[math]}$ then $\text{[math]}$ is a descendant of $\text{[math]}$ . we say $\text{[math]}$ is a proper ancestor of $\text{[math]}$ (and $\text{[math]}$ is a proper descendant of $\text{[math]}$ ) if $\text{[math]}$ is an ancestor of $\text{[math]}$ and $\text{[math]}$ . the depth of a node is the number of proper ancestors it has.
[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]

[cite:;refer to @graph_klein_2024 chapter 1 rooted forests and trees]