i need help programming 1.35 in racket with an accumulator (please make comments

Question

i need help programming 1.35 in racket with an accumulator (please make comments so I understand whats going on)

Exercise 1.34 [k**] Write a procedure path that takes an integer n and a binary search tree bst (page 10) that contains the integer n, and returns a list of lefts and rights showing how to find the node containing n. If n is found at the root, it returns the empty list. > (path 17 (14 (7 () (12 () )) (26 (20 (17 ) ()) (right left left) Exercise 1.35 [***] Write a procedure number-leaves that takes a bintree, and produces a bintree like the original, except the contents of the leaves are numbered starting from 0. For example, (number-leaves (interior-node 'foo (interior-node 'bar (leaf 26) (leaf 12)) (interior-node 'baz (leaf 11) (interior-node 'quux (leaf 117) (leaf 14)) should return (bar 0 1) (baz 2 (quux 3 4)))

Explanation / Answer

; Exercise 1.34

(define path
(lambda (n bst)
    (letrec
        ((loop
          (lambda (bst rev-path)
            (cond ((null? bst) (report-not-found))
                  ((< n (car bst)) (loop (cadr bst) (cons 'left rev-path)))
                  ((> n (car bst)) (loop (caddr bst) (cons 'right rev-path)))
                  (else (reverse rev-path)))))
         (report-not-found
          (lambda ()
            (eopl:error 'path "~s not found in BST ~s.~%" n bst))))
(loop bst '()))))
-----------------------------------------------------------------------------
; Exercise 1.35

; let-values and friends are not part of #eopl, so we simply use a pair.
(define number-leaves
(lambda (b)
    (letrec ((loop
              (lambda (b n)
                (if (leaf? b)
                    (cons n (+ n 1))
                    (let* ((bnl (loop (lson b) n))
                           (bnr (loop (rson b) (cdr bnl))))
                      (cons (interior-node (contents-of b) (car bnl) (car bnr))
                            (cdr bnr)))))))
      (car (loop b 0)))))

; See: exercise 1.31
(define leaf (lambda (i) i))
(define interior-node (lambda (s i1 i2) (list s i1 i2)))
(define leaf? integer?)
(define lson cadr)
(define rson caddr)
(define contents-of (lambda (b) (if (leaf? b) b (car b))))

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.