= Rooted tree
{wiki}
A <rooted tree> is a <tree> with a distinguished <vertex>, its <root of a tree> $r$. Choosing $r$ turns connections into a hierarchy: every other <vertex> has a unique <parent in a rooted tree>, the preceding <vertex> on its <graph path> from $r$. Conversely, the <vertices> whose <parent in a rooted tree> is $v$ are the <children in a rooted tree> of $v$. Choosing the <root of a tree> changes this description, while the underlying <edges> remain the same. Arrows towards the <root of a tree> can encode the relationship, as in MIT's counting notes; the undirected <tree> itself needs no arrows. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec05-06.pdf[MIT, Peter Shor's counting notes, pp. 3–4]{ref}
In the seven-<vertex> <tree> above, choose $r=1$. The levels, grouped by <graph distance> from the <root of a tree>, are $\{1\}$, $\{2,3\}$, $\{4,5,6\}$, $\{7\}$. The <children in a rooted tree> of $2$ are $4,5$, and the <parent in a rooted tree> of $7$ is $6$. Choosing $r=7$ instead makes the levels $\{7\}$, $\{6\}$, $\{3\}$, $\{1\}$, $\{2\}$, $\{4,5\}$: now $6$ has <parent in a rooted tree> $7$, reversing their relationship. All six <edges> survive.
This hierarchy supports <structural recursion>: process the smaller <rooted trees> below each <vertex>, then combine their results. A <depth-first traversal of a tree> explores one branch before returning; <breadth-first search> processes successive levels. The <lowest common ancestor> identifies where two routes from the <root of a tree> last coincide. For $4,5$ it is $2$ when $r=1$. A <binary tree> imposes an additional restriction on <children in a rooted tree>; a general <rooted tree> has no such bound.
Back to article page
