tree-equal function not giving the correct output

Question

I am writing code to test if two trees are equal (in data and structure) in Scheme, and I have to assume that I only have at most two children for each node. My code is as follows:

(define (make-tree value left right) 
  (list value left right))
(define (value tree)
  (car tree))  
(define (left tree) 
  (car (cdr tree)))
(define (right tree)
  (car (cdr (cdr tree))))

(define (tree-equal? T1 T2)
 (if (and (null? T1) (null? T2)) 
   #t
   (if (= (value T1) (value T2))
      (tree-equal? (left T1) (left T2))
      (tree-equal? (right T1) (right T2)))))

(tree-equal? '(1 2 3) '(1 2 3))

The output that I am getting is car:

 car: contract violation
 expected: pair?
 given: 2

Can anyone explain to me what I am doing wrong? Why is (value T1) giving this error? Should I rewrite my value function to check if the tree is null?

Answer 1

The problem leading to the error

There are a few places in your code where you could end up calling car with something that's not a pair, (and so violate the contract that car's argument should be a pair). One such thing, as the error message indicates, is 2. In particular, after checking that (= 1 1) (since 1 is the value of (1 2 3) and (1 3 2)), you recurse into the left branches of the trees with

(tree-equal? (left T1) (left T2))

Now, (left T1) produces 2, and (left T2) produces 3. Neither is null, so you end up getting to the following line with 2 == T1 and 3 == T2.

(= (value T1) (value T2))

Since value is defined as car, you're trying to call car with 2.

Some other issues…

After that's resolved, there are still some issues with your comparison function, some of which are simply stylistic, and some of which are actually going to cause problems.

(define (tree-equal? T1 T2)                   
 (if (and (null? T1) (null? T2))              
   #t                                         
   (if (= (value T1) (value T2))              
      (tree-equal? (left T1) (left T2))       
      (tree-equal? (right T1) (right T2)))))  

You're right to check that if both trees are null?, then they are the same. What happens if one of them is null? and the other isn't, though? You'll continue by calling value on (), which is no good. If the other isn't null?, but isn't a list either, you'll try calling value on it, and that would fail too. In the case that you do get two trees, and they happen to have the same value, then you check their left sides, and if they don't have the same value, you check their right sides. (This is how if works.) I expect that you really want to check that they have the same value and have the same left and have the same right.

You can actually simplify this with some boolean logic (the comments to the right should help). This uses a tree? predicate which you haven't defined yet, but it's not difficult, and it makes this code much easier to read.

(define (tree-equal? T1 T2)                       ; T1 and T2 are tree-equal iff
  (or (eq? T1 T2)                                 ; 1. are the same (this covers both being null), OR
      (and (tree? T1) (tree? T2)                  ; 2. a. both are trees, AND
           (eq? (value T1) (value T2))            ;    b. values are eq, AND
           (tree-equal? (left T1) (left T2))      ;    c. lefts are tree-equal, AND
           (tree-equal? (right T1) (right T2))))) ;    d. rights are tree-equal

On the traditional meaning of “tree” in Lisps

Now, I understand that you're using binary trees that have elements at each intermediate nodes, but I'll point out that “tree” is often used in Lisp contexts to denote an arbitrary structure built out of cons cells (i.e., pairs). The same approach can be used to compare them, but it's a little bit cleaner:

(define (tree-eq?  t1 t2)
  (or (eq? t1 t2)
      (and (pair? t1) (pair? t2)
           (tree-eq? (car t1) (car t2))
           (tree-eq? (cdr t1) (cdr t2)))))

This comparison function will, coincidentally, work for your type of tree as well, since one of your nodes has the form

(value . (left . (right . ())))

so the recursive calls would still end up processing the values, lefts, and rights from two trees at the same time. Of course, this would also recognize equivalent trees (in the traditional sense) that aren't actually legal trees (in the sense of your question). That's why it's important to have a corresponding tree? function (pair? serves just fine for the traditional case).