Rooted tree

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. ^[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.

A node with no children in a rooted tree. This depends on the chosen root: the root of a nontrivial tree can have undirected vertex degree one while still having a child and therefore not being a leaf in the rooted sense. In a single-node rooted tree, the root is a leaf. The distinction matters when counting the complement of the internal vertices of a rooted tree.

With every edge directed away from the root of a tree, a rooted tree leaf has outdegree zero.^[ref]

For an original example, take $E=\{ra,ab,ac\}$ and choose root$r$. The children of$r$ consist of$a$, and the children of$a$ are$b,c$. Thus$b,c$ are the rooted leaves. Vertex$r$ has undirected degree one but has a child, so it is not a rooted leaf in this rooting.

For a nonroot vertex$v$, one incident edge goes to its parent in a rooted tree, and all remaining incident edges go to children. ThereforeThe root instead satisfies $\mathrm{outdeg}(r)=\mathrm{deg}(r)$. A nonroot vertex is consequently a rooted leaf exactly when its undirected degree is one. The root is a rooted leaf exactly when the entire connected tree has one vertex.

Changing the root can change leaf membership without changing any edge. On the three-vertex path$a,b,c$, rooting at$a$ gives one rooted leaf$c$, while rooting at$b$ gives two, $a,c$.

A finite rooted tree always has a leaf: take a vertex maximizing its graph distance from the root. Any child would lie one edge farther away, contradicting maximality. An infinite ray rooted at its endpoint has a child at every vertex and supplies the corresponding counterexample to an unrestricted infinite-tree claim. Rooted terminal points and endpoints of an unrooted graph therefore need their conventions stated explicitly.

A root-to-leaf path is the unique simple graph path from the root of a tree to a rooted tree leaf. Successive vertices follow parent-to-child relationships. If the rooted tree has only one vertex, its root is also its leaf and the path has zero edges.^[ref]

For an original example, root the tree with $E=\{ra,ab,ac,cd\}$ at$r$. Its rooted leaves are$b,d$, and its complete root-to-leaf paths areTheir lengths are two and three edges. The first two vertices form a shared prefix; the shared route ends at$a$ before the paths enter different descendant branches. Counting only the endpoint labels would omit that shared ancestry.

Uniqueness follows from the absence of a graph cycle. Two different simple routes from the root to one leaf would separate and later rejoin, producing a cycle. Conversely, following a leaf's successive parent in a rooted tree backward must recover its one root path.

If all vertex identities and complete root-to-leaf paths of a finite tree are known, their consecutive vertex pairs recover its edges. Every vertex lies on such a path: from it, keep selecting a child until finiteness forces a leaf. A list of path lengths alone supplies much less information; it discards vertex identities and the locations where paths share prefixes.

The edge count is the endpoint's depth in an unweighted rooted tree. A drawing's Euclidean arc length or a sum of assigned edge lengths is an additional measurement. Two drawings of the same rooted tree can therefore have identical root-to-leaf vertex lists and different geometric lengths.

A rose tree is an ordered rooted tree in which each vertex can have any finite number of children in a rooted tree. A labelled Haskell representation is data RTree a = Node a [RTree a]. Its tree fold has type (a -> [b] -> b) -> RTree a -> b: recursively fold the children, then combine their results with the current label. Unlike a binary tree, a rose tree has no fixed pair of child positions.

A rose tree is perfect when all its leaves of a rooted tree have the same depth. This permits unequal branching counts and unary branches; perfectness alone does not require every internal vertex to have the same number of children. A bottom-up certificate returns Just 0 at a leaf, Just (h+1) when all child certificates are Just h, and Nothing otherwise. Structural induction proves that a certificate exists exactly when the tree is perfect: all root-to-leaf routes acquire one edge when attached to the new root.

A vertex reachable from a specified vertex by following child edges in a rooted tree. Allowing the length-zero graph path includes the starting vertex; a proper descendant excludes it. The subtree at a vertex consists of that vertex and its descendants. State the properness convention when using strict discovery-time inequalities.

Two distinct vertices are siblings when they have the same parent in a rooted tree.

A vertex with at least one child in a rooted tree. Internal vertices and leaves of a rooted tree partition the vertex set. The ancestors of an internal vertex are also internal; consequently the internal vertices of a nontrivial rooted tree induce a connected subgraph containing its root.

A rooted tree in which every internal vertex has exactly three tree children. For a finite rooted tree with $m$ tree leaves and internal outdegrees $d_v$, counting edges in two ways givesIndeed, the number of edges is the total number of vertices minus one and also the sum of the internal outdegrees. Thus a full ternary tree with $N$ internal vertices has $m=1+2N$ tree leaves, always an odd number. More generally, if every internal vertex has either two or three tree children, $m=1+N_2+2N_3$. This parity controls the initial merge in ternary Huffman coding.

A full ternary tree whose leaves all have the same depth. At depth $j$ there are $3^j$ vertices, so a tree with $h+1$ levels has $N_h={\sum }_{j=0}^h{3}^j=(3^{h+1}-1)/2$ vertices and $3^h$ leaves, by the finite geometric series formula. For a rose tree representation, recursively flattening children and joining their lists with ordinary list concatenation copies each label once per ancestor. The work is therefore $\Theta ((h+1)3^h)=\Theta (N_h\log N_h)$ when the complete output is demanded. Passing an already constructed suffix through the recursion instead emits each label once, giving $\Theta (N_h)$ work.

A Fibonacci tree is a recursively defined binary tree whose two subtrees have consecutive smaller orders. One convention sets $T_0$ and $T_1$ to a single vertex and defines $T_n$ for $n\ge 2$ by attaching $T_{n-1}$ and $T_{n-2}$ to a new root. Then its vertex count satisfies $N_n=1+N_{n-1}+N_{n-2}$, so $N_n=2F_{n+1}-1$ for Fibonacci numbers $F_0=0,F_1=1$. The counts begin $1,1,3,5,9$. Initial trees vary across applications, so the convention must be stated; the common feature is the consecutive-order recursive branching.

The distinguished vertex that specifies a rooted tree. Its choice determines the parent in a rooted tree and children in a rooted tree relationships.

For a nonroot vertex, its adjacent predecessor on the unique graph path from the root of a tree. The root of a tree has no parent.

A vertex whose parent in a rooted tree is the specified vertex.

The exponential generating function for labelled rooted trees satisfies $T=z{e}^T$: remove the root and obtain an unordered set of smaller labelled rooted trees. For $0\le z<1/e$, the convergent series is the solution in $[0,1)$ of $T{e}^{-T}=z$, rather than the larger real solution. Alternatively, tree-component expectation in the Erdős-Rényi model and subcritical exploration give $T(\theta e^{-\theta })=\theta$ for $0<\theta <1$: their limiting probabilities for the order of the tree component of a uniform vertex sum to one. The component tail bound makes this passage through the infinite sum valid.

For finite rooted trees in the ancestor partial order, a rooted-tree homeomorphic embedding is an injective vertex map preserving lowest common ancestors: $h(u\wedge v)=h(u)\wedge h(v)$. The image of the source root need not be the host root. Edge paths and branching are preserved, while paths may be subdivided in the larger tree.

Give a leaf rank zero, and use Hessenberg natural sum over the immediate rooted subtrees. Every rank is below epsilon zero; conversely repeated exponentiation and finite summation encode every Cantor normal form below it. A rooted-tree homeomorphic embedding implies nondecrease of the rank. When roots match, child subtrees embed into distinct branches and exponentiation and natural sum preserve their inequalities. When the source root maps below the host root, its rank is bounded by that of a proper subtree, strictly below the host rank.

An adjacency-preserving rooted-tree embedding is an injective vertex map preserving the root and every adjacency. Because each root-to-vertex path maps to a simple path of the same length, vertex depths are preserved. This is more restrictive than a homeomorphic embedding of a rooted tree, which may stretch edges into paths. The branching-depth antichain of rooted trees shows that the adjacency relation is not a well-quasi-ordering.

Let $T_m$ consist of a rooted path of $m\ge 1$ edges followed by two leaves at its far end. Its only vertex with two children has depth $m$. An adjacency-preserving rooted-tree embedding must preserve this depth, so $T_m$ embeds into $T_n$ only when $m=n$. This gives an infinite bad sequence, while rooted-tree homeomorphic embeddings can stretch the stems.

For rooted trees labelled in a preorder $Q$, a label-monotone tree embedding is a homeomorphic embedding of a rooted tree whose vertex map satisfies ${\ell }_T(v){\le }_Q{\ell }_S(h(v))$. The root need not map to the host root. For ordered child lists, require in addition that the map preserve the relative order of distinct branches.

The lowest common ancestor of two vertices is the common ancestor farthest from the root. In the ancestor partial order with the root least, it is their infimum, also called their greatest common ancestor.

For a label set $D$, define $\mathcal{T}(D)$ inductively: choose a root label $d\in D$ and a finite repetition-free sequence of rooted trees in $\mathcal{T}(D\setminus \{d\})$ as its children. Each object is a finite ordered rooted tree. Labels are distinct along each root-to-leaf path, and child rooted trees at a vertex are distinct as whole rooted trees. Labels may repeat across different branches; children need not have distinct root labels. For a finite pool of size $m$, the exact number $t_m$ of rooted trees satisfiesThis follows by choosing the root and then an ordered repetition-free list from the finite pool of smaller rooted trees.

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

For an automorphism $g$ of a regular rooted tree and a first-level vertex $i$, the section $g_i$ is the induced automorphism of the rooted subtree at $i$, defined byAn automorphism fixing the first level is determined by the tuple of all its sections.