CODEWITHSUNDEEP
scheme
Evan S
Evan S

Reputation: 191

Scheme remove left and right children if they are null

I am trying to write scheme code (DrRaket or MIT) that remove left and right children if they are null.

;;definition of make-tree;;

(define (make-tree entry left right)
  (list entry left right))

;;input tree;;

(define tree (8 (5 (2 () ()) (4 () ())) (3 () (10 () ()))))

if I do (print tree) suppose to change the input tree to

;;expected output;;

(8 (5 (2)(4)) (3 () (10)))

;;

(define (print tree)
  (cond ((and (null? (cadr tree)) (null? (caddr tree)))
         (cons (car tree) '())
         (make-tree (car tree) (cadr tree) (caddr tree))
         (print tree)
         )))

But I get linefeed after attempting (print tree). Could someone help me get the expected output?

In reply to soegaard 33's solution

(define (prune tree)
  (cond tree
    ((list x '()  '())    (list x))
    ((list x left '())    (list (prune left) (list x)))
    ((list x '()  right)  (list              (list x) (prune right)))
    ((list x left right)  (make-tree x (prune left) (prune right)))))

Output
Welcome to DrRacket, version 6.1.1 [3m].
Language: R5RS; memory limit: 128 MB.
. tree: bad syntax in: tree
>

Upvotes: 2

Views: 98

Answers (1)

soegaard
soegaard

Reputation: 31147

This solution uses match from Racket.

(define (prune tree)
  (match tree
    [(list x '()  '())    (list x)]
    [(list x left '())    (list (prune left) (list x))]
    [(list x '()  right)  (list              (list x) (prune right))]
    [(list x left right)  (make-tree x (prune left) (prune right))]))

The tree has four different shapes.

Each clause handles a different shape.

If you can't use match change it to a cond with four cases.

Update:

(match tree
  ((list x '()  '())    (list x))
  ...
  ...)

becomes

(cond 
  ((and (list? tree) 
        (null? (cadr tree))     ; the second element is '()
        (null? (caddr tree)))   ; the third  element is '()
   (list x))
  ...
  ...)

Upvotes: 1

Related Questions