Path in binary tree

Question

I'm preparing for my exams and I did almost everything, but this exercise I don't understand. How to make a function that will search for a path in a binary tree from a specific value.

Here is an example:

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))
(find-path tree 4)
(1 2 4)

Answer 1

I start sketching out some code -

(define (find t q) ;; find q in t

(path empty) ;; the return path will be a list, we'll start it off as an empty list

(if (empty? t) ;; fundamental laws: always check for empty list first
    #f         ;; if the tree is empty, there is nothing to find, we use #f to signal this
    (if (eq? q (car t)) ;; otherwise we can check if the node matches q ...
        ;; wups we can't do eq? test yet, it's possible `(car t)` is a list of nodes
        ))

How do I see this? I look at our input list -

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))

1. We always check for empty? first
2. If the list is not empty, we know we have:
   • at least one element, (car tree)
   • the rest of the elements, (cdr tree)
3. I visualize the elements of the outermost list; there are only three:
   • 1
   • (2 (3) (4))
   • (5 (6 (7) (8)) (9))
4. The first element was 1 so I thought I could reach for eq? and check if it matched q right away
5. I noticed the second element was a different type. Intuitively we cannot match a single element against a list of elements, so we must handle the list? case before we attempt eq?

Fix my boo boo -

(define (find t q)

(path empty)

(if (empty? t)
    #f
    (if (list? (car t))
        ;; when the node is a list of nodes
        (if (eq? q (car t))
            ;; when the node matches q
            ;; when the node does not match q
            )))

Collapse chained if to cond for better readability -

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       )
      ((eq? q (car t))
       ;; when the node matches q
       )
      (else
       ;; when the node does not match q
       ))

The code is flatter and nicer to read now. Some of those blanks are tricky to fill in, but I am drawn to the second blank; when q equals(car t) that means we found a match and it's time to return the path -

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       ;; we'll come back to this ...
       )
      ((eq? q (car t))
       (cons q path)) ;; return the path with the final node
      (else
       ;; when the nodes does not match q
       ;; and save this for later too ...
       ))

Ok, that wasn't so bad. So I checked when (car t) matches q, now I have to say what happens when it doesn't match. When (car t) doesn't match, I'll add it to the path and somehow check to see if q matches any of the node's children, (cdr t) -

(define (find t q)

(path empty)

(cond ((empty? t)
        #f)
      ((list? (car t))
       ;; when node is a list of nodes
       ;; we'll come back to this ...
       )
      ((eq? q (car t))
       (cons q path))
      (else

       ;; add the node to the path ...
       (cons (car t) path)

       ;; check the node's children for a match
       (find (cdr t) q)

       ;; this doesn't quite work ...
       ))

I run into a situation where we need to update path with the new node and I need to call find which does not have path parameter. To remedy this, I introduce a loop which allows us to repeatedly evaluate an expression with any arguments we specify -

(define (find t q)

(let loop ;; lazily and sloppily insert a named loop

((path empty) ;; initialize the parameters that will change
 (t t))

(cond ((empty? t) ;; the expression to repeat, (cond ...)
        #f)
      ((list? (car t))
       ;; when the node is a list of nodes
       )
      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path) ;; updated path
             (cdr t))))          ;; updated tree

The else clause taught me how to match against a node's children, which is a list of nodes. That will certainly make it easier to deal with that last blank in the code, which is what to do when the node is a list of nodes! -

(define (find t q)

(let loop

((path empty)
 (t t))

(cond ((empty? t)
        #f)
      ((list? (car t))

       ;; we could just recur the loop with 
       (loop path
             (car t))

       ;; but what about (cdr t) in this case?
       (loop path
             (cdr t))

      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path)
             (cdr t))))

The final problem here is I have two (2) lists to check; (car t) is determined to be a list, and (cdr t) is a list. I must check both of them. The simple solution is to combine the two loop calls with or. If one loop returns #f, the other will be checked -

(define (find t q)

(let loop

((path empty)
 (t t))

(cond ((empty? t)
        #f)
      ((list? (car t))
       (or (loop path   ;; or represents dysjunction!
             (car t))
           (loop path
             (cdr t))))
      ((eq? q (car t))
       (cons q path))
      (else
       (loop (cons (car t) path)
             (cdr t))))

Fix up the parentheses, run the automatic indenter -

(define (find t q)
  (let loop
    ((path empty)
     (t t))
    (cond ((empty? t)
           #f)
          ((list? (car t))
           (or (loop path
                     (car t))
               (loop path
                     (cdr t))))
          ((eq? q (car t))
           (cons q path))
          (else
           (loop (cons (car t) path)
                 (cdr t))))))

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))

(find tree 4)
;; '(4 2 1)

(find tree 8)
;; (8 6 5 1)

(find tree 9)
;; (9 5 1)

Observe that the result is reversed because indeed the path is constructed in reverse order. The exit condition that returns the path simply needs call reverse before returning -

(define (find t q)
  (let loop
    ((path empty)
     (t t))
    (cond ((empty? t)
           #f)
          ((list? (car t))
           (or (loop path
                     (car t))
               (loop path
                     (cdr t))))
          ((eq? q (car t))
           (reverse (cons q path))) ;; don't forget to reverse!
          (else
           (loop (cons (car t) path)
                 (cdr t))))))

(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))

(find tree 4)
;; '(1 2 4)

(find tree 8)
;; (1 5 6 8)

(find tree 9)
;; (1 5 9)