Proving that a preorder traversal of a rooted tree can be performed in linear time 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 &gt; 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?
You can prove that formally by using structural induction. The structure of the proof is as follows:

Observe that a preorder traversal of a tree with $1$ vertex requires constant time.

Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the preorder traversal of a tree $T$ with $i+1$ vertices requires at most $c \cdot (i+1)$ time. Here you use the induction hypothesis and the definition of the traversal. In particular, notice that the subtrees of $T$ that are rooted in the children of the root have at most $i$ vertices.