Proving that a preorder traversal of a rooted tree can be performed in linear time
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.