$1\mathrm{.}1$ Depth First Search $+$ Extended List $[8$ pts$]$

Use Depth First Search with an Extended List to find both the path and the extended node list. Use this space to draw the corresponding tree and show your work. Mark each node as you extend it by putting a number in a circle next to the node corresponding to when it was extended. How many times does your search backtrack? Search Tree:

Node extension order is given in circles at the top$-$left of the corresponding node.

Path:

SBCFAEG

Extended Nodes in order Extended:

SBCDFAEG

Number of backtracks:

$1$