Exercise $2.$ Computing Parents in Search Tree

We want to modify DFS so it stores, for each node, its parent in the search tree $($the parent of the root is NULL$).$

a$)$ Show the DFS example from Exercise $1-$b with a value to the right of each node showing its parent.

b$)$ Take the DFS pseudocode from Chapter $13$ and add the code to it for computing parents. Show the resulting algorithm, circling your new code. Make sure the algorithm is correct $($i$.$e$.$ it actually computes the values you showed in $($a$)).$ Note: Your algorithm should still be $O(m+n).$

c$)$ Show the BFS example from Exercise $1-$c with a value to the right of each node showing its parent.

d$)$ Take the BFS pseudocode from Chapter $13$ and add the code to it for computing parents. Show the resulting algorithm, circling your new code. Make sure the algorithm is correct $($i$.$e$.$ it actually computes the values you showed in $($c$)).$ Note: Your algorithm should still be $O(m+n).$