TAOCP 2.3.4.2 Exercise 12
The degree of a node in the tree terminology of Section 2.
Section 2.3.4.2: Oriented Trees
Exercise 12. [**] $$M10$$ In the correspondence between oriented trees as defined here and oriented trees as defined at the beginning of Section 2.3, is the degree of a tree node equal to the in-degree or the out-degree of the corresponding vertex?
Verified: yes
Solve time: 1m13s
The degree of a node in the tree terminology of Section 2.3 is the number of children of that node. In the corresponding oriented tree, every arc is directed from a vertex toward its parent. Therefore the children of a vertex $V$ are precisely those vertices $W$ for which $e[W]$ has final vertex $V$.
Hence the number of children of $V$ is the number of arcs whose final vertex is $V$, namely the in-degree of $V$. The out-degree is $1$ for every nonroot vertex and $0$ for the root, so it does not represent the degree of the node.
Therefore the degree of a tree node is equal to the corresponding vertex's in-degree.
$$ \boxed{\text{degree}=\text{in-degree}} $$