<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>