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 > 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 may need assumptions such as getting from $T$ (or $r$) to any of the subtrees takes time bounded above by a constant. (You may be making this in does constant work on each visit.) It's too obvious suggest by contradiction, each by induction. – greybeard Feb 26 at 7:46
• It is actually hard to see what is really assumed about trees, and what is to prove here? Usually we show complexity results given a representation of the data structure (here nodes and edges). Then we reason about the number of steps it takes it takes to collect information or move to certain nodes via edges. Below, in the structural induction proof, I see none of these. – Hendrik Jan Feb 27 at 23:12

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.

• This is what I was looking for. Makes perfect sense, thanks @Steven. – tossimmar Feb 26 at 0:22

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.

• Thanks @D.W. I did prove correctness using structural induction... didn't think to use it again to prove runtime. Makes perfect sense. Thanks. – tossimmar Feb 26 at 0:23