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
Related Tags
trees × 706algorithms × 275
graphs × 208
data-structures × 192
binary-trees × 110
search-trees × 50
graph-traversal × 43
search-algorithms × 27
optimization × 25
recursion × 25
balanced-search-trees × 22
algorithm-analysis × 21
terminology × 21
combinatorics × 21
dynamic-programming × 19
time-complexity × 18
heaps × 14
minimum-spanning-tree × 14
spanning-trees × 14
complexity-theory × 13
shortest-path × 13
discrete-mathematics × 12
binary-search-trees × 12
reference-request × 10
sets × 9