# Tag Info

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