$10\%$

$($a$)$ Consider the following $m-$ary tree and answer the following questions.

$($i$)$ List the sequence of vertices being visited using the pre$-$order traversal.

$($ii$)$ List the sequence of vertices being visited using the post$-$order traversal.

$($iii$)$ List the sequence of vertices being visited using the in$-$order traversal.

$($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 $($i$.$e$.,$ both sequences of vertices visited$)$ of a binary tree, design an algorithm to re$-$construct the tree or prove that this is not possible.