**Definition:**

Let $T(V, E)$ be a rooted tree with root $r$.

If $T$ has no other vertices, then the root by itself constitutes the *preorder traversal* of $T$.

If $\lvert V \rvert > 1$, let $T\_1, T\_2, \dots, T\_k$ denote the subtrees of $T$ from left to right. The *preorder traversal* of $T$ first visits $r$ and then traverses the vertices of $T\_1$ in preorder, then the vertices of $T\_2$ in preorder, and so on until the vertices of $T\_k$ are traversed in preorder.

**Question:**

How does one prove, using the above definition, that a preorder traversal of a rooted tree $T(V, E)$ can be computed in $O(\lvert V \rvert)$ time? Since $T$ is a tree, $\lvert E \rvert = \lvert V \rvert - 1$, and so showing that a preorder traversal algorithm simply visits the vertices and edges of $T$ a constant number of times and does constant work on each visit would do it. Obviously this is true, but how does one prove this formally?