Recursive breadth first tree traversal

Question

I'm pulling my hair out trying to figure out how to implement breadth first tree traversal in scheme. I've done it in Java and C++. If I had code, I'd post it but I'm not sure how exactly to begin.

Given the tree definition below, how to implement breadth first search using recursion?

(define tree1 '( A ( B (C () ()) (D () ()) ) (E (F () ()) (G () ())) ))

Any help, any, is greatly appreciated.

Answer 1

I bet when you did this in other languages you used a stack for dfs and a queue for bfs. When you do depth first search, you're fundamentally using a stack to decide which node to explore next, and recursion gives you a function call stack, so it's easy to conceptualize how the two mirror each other. With breadth first search, the question becomes, how do you traverse a queue recursively?

Now recall that anything you can do iteratively, you can do recursively. Where you might write "while x < 10: x += 1", you can instead write

(define (my-loop x)
  (if (< x 10)
      (my-loop (+ x 1))
      ... ;; your base case
      ))

and suddenly you're doing the iteration recursively. Great.

So we have this queue. We put things on one end, take things off the other. Just like we passed around the loop control variable x in the loop above, you'll have to explicitly pass around the queue. In the next "iteration", which becomes now the next level of recursion, you'll want to have put some new children on the queue, and that next recursion will take one child off the other end of the queue, or stop (return) if there are no more children.

Now the call stack no longer mirrors your location in the tree, so it's hard to see why recursion would be better or more intuitive, but it's always possible.

Hope that helps,
Grem

Answer 2

you could do something like this: have a recursive helper function that goes to depth n, and concats the elements with a row... the output would be a list with all elements of the tree at depth n.

(defun findAtN (tree n)
(cond ((equal tree nil) nil)
      ((equal (n 0)     (car tree))
      (t                (append (findAtN (cadr tree) (- n 1))
                                (findAtN (caddr tree) (- n 1))))))

then a second function that increases the depth, searching each level for a given node.

(defun ContainsElt (tree Elt n)
(cond ((equal (findAtN tree n) nil)   nil)
      ((member Elt (findAtN tree n))  true)
      (t                              (ContainsElt tree Elt (+ n 1)))))

This is untested and probably slightly different based on your parameters/dialect of lisp, as well as if you want to do more than just test if an item is in the tree, but maybe it'd help with an idea how to do it.

Answer 3

0) Is this homework? If so, stop reading :).

BFS algorithm: if the queue is empty, give up. Otherwise, separate the queue into first and remaining, check to see if the first is the one you want, otherwise recur with a queue containing the remaining elements and all of the newly reachable ones.

Of course, I can "say" the same sentence in Scheme:

#lang scheme

(define (bfs pred queue)
  (match queue
    [empty #f]
    [(cons elt queue-rest) 
     (or (pred elt)
         (bfs pred (append queue-rest (remove* queue-rest (reachable-from elt)))))]))

1) totally untested, almost surely buggy (altho not in the measure-theoretic sense :))

2) you need your own representation of graphs & "reachable-from".

3) lists aren't a great queue implementation.