Proving that a preorder traversal of a rooted tree can be performed in linear time

Question

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?

Answer 1

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.

Answer 2

You have to do three things:

1. Exhibit an algorithm.
2. Prove that it is correct (it outputs the right value).
3. Prove that its running time is $O(|V|)$.

@Steven describes one way to prove the running time.

One can probably prove correctness using structural induction as well.