$($b$)$ Prove that the pre$-$order traversal algorithm given in the lecture runs in $O(n)$ time, where $n$ is the number of vertices in the tree.

$($c$)$ Given the pre$-$order and post$-$order traversal $($ie$.$both sequences of vertices visited$)$ of a binary tree, design an algorithm to re$-$construct the tree or prove that this is not possible.