2
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 ...
2
A tree structure can be completely described by three functions:
a function that given a node $x$ returns the number of children of that node,
a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
a function that given a node $x$ returns an associated value $v$ stored at that node.
1
You have to do three things:
Exhibit an algorithm.
Prove that it is correct (it outputs the right value).
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.
Only top voted, non community-wiki answers of a minimum length are eligible
