to find a person's descendants of a binary family tree (scheme lang)

Question

this is a scheme program to find the descendants of a binary family tree (the tree has only fathers and two sons - bst) when a person's name and the tree is given as input. I think the main problem here is the getsons function. What should I replace this function with?

(define (getfather FAMT)`
  (car FAMT)
   )


 (define (getson1 FAMT)
  (cadr FAMT)
 )

 (define (getson2 FAMT)
  (caddr FAMT)
 )

 (define (getsons FAMT)
 (cdr FAMT)
 )

 (define (empty? FAMT)
 (null? FAMT)
 )

(define (nosons? FAMT)
 (and (empty? (getson1 FAMT)) (empty? (getson2 FAMT)))
)

(define (getd FAMT)
 (cond ((empty? FAMT) '())
       ((nosons? FAMT) '())
       ((empty? (getson1 FAMT)) (getson2 FAMT))
       ((empty? (getson2 FAMT)) (getson1 FAMT))
       (else (getd (getsons FAMT))))
 )

(define (main1 person FAMT)
 (cond ((empty? FAMT) (getd '()))
       ((equal? person (getfather FAMT)) (getd FAMT))
       (else ( main1 person (getsons FAMT))))
 )



(define FAMT '(Pierce (Mark (Peter () ()) (Blaise () ())) (James () () )))

</code>

Answer 1

Both getd and main1 are incorrect. In getd, the cases where one of the sons is missing must recursively call getd on the other son, and the else case must recursively call getd on both sons and combine the answer. And anyway, the solution is too complex, only two cases are truly required, either the tree is empty or is non-empty, the whole trick lies in knowing how to combine the answers from both subtrees, I chose to append the elements to create an output list:

; returns a list of all descendants, including node at the root
(define (getd FAMT)
  (cond ((empty? FAMT)
         '())
        (else
         (append (list (getfather FAMT))
                 (getd (getson1 FAMT))
                 (getd (getson2 FAMT))))))

Similarly, main1 must combine the results of both sons once a person is found, and it must keep recursively looking on both sides of the tree and combine its answers, because we don't know at which side is the searched person (the tree doesn't seem to be sorted):

; finds a person and returns a list with all of
; its descendants, the list excludes the person
(define (main1 person FAMT)
  (cond ((empty? FAMT)
         '())
        ((eq? person (getfather FAMT))
         (append (getd (getson1 FAMT))
                 (getd (getson2 FAMT))))
        (else
         (append (main1 person (getson1 FAMT))
                 (main1 person (getson2 FAMT))))))

Finally, you should use larger trees for testing, the sample tree in the question doesn't cover all possible cases, for instance:

(define FAMT 
  '(Pierce
    (Mark 
     (Peter 
      (Logan () ()) 
      ()) 
     (Blaise 
      () 
      (Kurt () ())))
    (James 
     ()
     ())))

(main1 'Mark FAMT)
=> '(Peter Logan Blaise Kurt)