<div dir="ltr">I'm trying to do a simple depth-first search of a tree in Racket, ultimately returning a list of nodes up to the node I'm searching for. I want to do this side-effect-free, if possible, and I'm running into a wall with the approach I started on...<div>


<br></div><div>This is my current implementation:</div><div>-------------------Begin Code---------------------------</div><div>#lang racket</div><div>(define example-tree '("E"†</div><div>† † † † † † † † † † † † † † † † †("B"</div>

<div>† † † † † † † † † † † † † † † † † †("S"))</div>
<div>† † † † † † † † † † † † † † † † †("U"†</div><div>† † † † † † † † † † † † † † † † † ("V")†</div><div>† † † † † † † † † † † † † † † † † ("T"†</div><div>† † † † † † † † † † † † † † † † † † ("H"†</div>


<div>† † † † † † † † † † † † † † † † † † † ("G"))))))</div><div><br></div><div><div>(define (parents node tree branch backtrack)</div><div>† (letrec ([children (if (pair? tree)</div><div>† † † † † † † † † † † † †(cdr tree)</div>

<div>† † † † † † † † † † † † †'())]</div><div>† † † † † †[extended-branch (cons (car tree) branch)]) ;optimistically add it to the working branch</div><div>† † (cond†</div><div>† † † [(equal? node (car tree)) branch] ; found the node, return the branch</div>

<div>† † † [(empty? children) (backtrack)]</div><div>† † † [else (parents ;the recursive case</div><div>† † † † † † †node † †;still looking for the same node</div><div>† † † † † † †(car children) ;search the first child node</div>

<div>† † † † † † †extended-branch</div><div>† † † † † † †(if (> (length children) 1)</div><div>† † † † † † † † †(Ž () (parents node (cdr children) extended-branch backtrack)) ;store the search</div><div>† † † † † † † † †backtrack))])))†</div>

<div><br></div><div>(parents "H" example-tree '() (Ž () "Node Not Found"))</div></div><div><br></div><div>---------------------End Code----------------------------------</div><div>The output I should see is '("T" "U" "E")</div>

<div><br></div><div>The output I get is "Node Not Found"</div><div><br></div><div>I've been debugging in Dr. Racket, and the confusion sets in when calling backtrack after hitting node "S". It appears to do what I expect--calls†</div>

<div>(parents "H" †'("U" ("V") ("T" ("H" ("G"))))) '("E") †(Ž () "Node Not Found"))</div><div><br></div><div>I think... I'm not so sure about the value of the final argument, backtrack, here. Is there a way to examine the procedure in more detail from the debugger?</div>

<div><br></div><div>Anyhow, this is all more or less what I intended with the code, but stepping through this call to parents does not continue as I had hoped. Children is bound to '() though I would have expected '(("V") ("T" ("H" ("G"))). extended-branch is bound to †'(("U" ("V") ("T" ("H" ("G")))) †("E")), where I would have expected ("U" "E").†</div>

<div><br></div><div>So, the number one question is, does this general approach even make sense? If so, is the problem here in the logic (still kinda rough, I know) or am I†cdring†where I ought to be cadring in some†spot? Or if this approach is a non-starter, where should I look for a way to do this? Thanks for the help.</div>

<div><br></div><div><br></div><div><br></div></div>