Scheme/Racket Operations in Binary tree (+, -, *, /)

Question

how can I make a function that operates 2 binary trees? for example if the operation is “+”, the n-esim number of every node of the resultant tree will be the sum of the n-esim number of the 1st tree with the n-esim number of the 2nd tree, considering the same structure for each node (if the node is a list the sum would be a list, if the node is number the result would be a number, etc).

Here is an example:

(operate "+" ’((1 2)((2 3) null null) null) ’((0 2)((1 4) null null) null))

the return should be:

’((1 4) ((1 7) null null) null)

Note: the representation is (Father (leftSon)(rightSon))

uselpa uselpa · Accepted Answer · 2014-11-21T22:58:09

There are a few fishy things about your question:

the operation + should not be a string
the way you express your list, null is actually the symbol null and not the empty list
your elements are not consistently represented as (father leftSon rightSon)
2 + 3 is 5 so the result you give seems incorrect

but assuming this is really what you want, it's a simple list traversal:

(define (operate fun sxp1 sxp2)
  (cond
    ((null? sxp1) sxp1)     ; the real empty list
    ((eq? 'null sxp1) sxp1) ; the symbol null
    ((pair? sxp1) (cons (operate fun (car sxp1) (car sxp2))
                        (operate fun (cdr sxp1) (cdr sxp2))))
    (else (fun sxp1 sxp2)))) ; atom => apply fun to elements

Testing:

> (operate + '((1 2) ((2 3) null null) null) '((0 2) ((1 4) null null) null))
'((1 4) ((3 7) null null) null)

Scheme/Racket Operations in Binary tree (+, -, *, /)

1 Answers