def grid$\_$search$($xTr$,$ yTr$,$ xVal, yVal, depths$)$:

$"""$

Calculates the training and validation loss for trees trained on xTr and validated on yTr with a number of depths.

Input:

xTr: nxd training data matrix

yTr: n$-$dimensional vector of training labels

xVal: mxd validation data matrix

yVal: m$-$dimensional vector of validation labels

depths: a list of len k of depths

Output:

best$\_$depth, training$\_$losses, validation$\_$losses

best$\_$depth: the depth that yields that lowest validation loss

training$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the training loss of the tree of depth$=$depths$[$i$]$

validation$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the validation loss of the tree of depth$=$depths$[$i$]$

$"""$

training$\_$losses $=[]$

validation$\_$losses $=[]$

best$\_$depth $=$ None

# Initialize the variable

best$\_$loss $=$ float$(\text{'}$inf$\text{'})$

# Loop over all possible depths for the regression tree

for dept in depths:

# Check if the current validation is less than the best validation loss

if validation$\_$loss $<$ best$\_$loss:

best$\_$loss $=$ validation$\_$loss

best$\_$depth $=$ depth

raise NotImplementedError$()$

return best$\_$depth, training$\_$losses, validation$\_$losses