Sunday, December 21, 2008

Valid and Equal Binary Tree Scheme

This is one possible way of determining whether two binary trees are equal. Granted this implementation is dependent on them being valid. Which is that they are both symmetric around the top head node.

(define (valid-bintree? t)
(if (null? t)
#t
(if (list? t)
(if (valid-bintree? (car t))
(if (valid-bintree? (caddr t))
#t
#f)
#f)
#f)
))

(define (equal-bintrees? a b)
(if (null? a)
(if (null? b)
#t
#f)
(if (null? b)
#f
(if (and (valid-bintree? a) (valid-bintree? b))
(and (= (cadr a) (cadr b)) (equal-bintrees?(car a) (car b)) (equal-bintrees?(caddr a) (caddr b)))
#f)
)
))

No comments: