Tree depth: car/cdr contract violation

Question

I'm using racket to return the depth of a given tree. Here's the current code:

(define (depth tree)
   (cond
      [(empty? tree) 0]
      [else
       (+ 1 (max (depth (cadr tree))
                 (depth (caddr tree))))]))

I haven't been able to test it though because I always get a run-time error about violating the contract of car and cdr. To be specific, when I try

(depth '(1 2 3))

which should return 1, I encounter:

length: contract violation
  expected: list?
  given: 2

No matter what I do, the problem stays, and I'm not allowed to change the test case to fix the problem. I'm sure it's simple, but could someone please help me understand?

(I've looked at other posts; some discuss the algorithm of depth but I'm asking specifically about the car/cdr contract violation as presented here.)

Answer 1

The answer to your question is contained in your base case: empty?. What is '()? It is the end of a list. So if you want to know the depth, you need to be sure that you recur on any lists inside of the list in question.

Here is what you are asking as I read the code: if tree has some element, then take the maximum of the depth of that element compared to the depth of the next element. What you probably wanted to ask was to take the maximum of the depth of that element with the depth of the rest of the list (this is not caddr it is cdr). So I assume you will want to give the depth of 2 as zero (it isn't a list). If so, have you properly listed such a case in your cond tests? Hmm. Maybe there's a way to check if something is a pair, in which case we recur, otherwise it's of depth 0...

Answer 2

There are potentially a couple of issues here.

First and most important: the error you're pasting has to do with "length", but there aren't any uses of "length" in your program. When I run your code, here's the error I get:

cadr: contract violation
  expected: (cons/c any/c pair?)
  given: 2

The best way to understand what's going on here might be to use the stepper. To be more specific: set the language level to "Beginning Student with List Abbreviations", put the following program in the definitions window, and click "step":

(define (depth tree)
   (cond
      [(empty? tree) 0]
      [else
       (+ 1 (max (depth (cadr tree))
                 (depth (caddr tree))))]))

(depth '(1 2 3))

Answer 3

Short Answer:

Use pair? instead of empty? and switch the clauses. Giving you:

(define (depth tree)
   (cond
      [(pair? tree)
       (+ 1 (max (depth (cadr tree))
                 (depth (caddr tree))))]
      [else 0]))

Long Answer

The problem is your use of cadr and caddr, as you can see when you run your given example:

The actual error being:

cadr: contract violation
  expected: (cons/c any/c pair?)
  given: 2

This is because you're only checking empty?, which returns #t only when given an empty list. A number like 2 is NOT an empty list, so it returns #f, and it moves onto the second case, where you try to take the cadr of an empty list. Obviously this is going to fail.

Checking to see if something is a pair? gets you the actual case you want.

In general, you'll be much better off taking a step back and actually thinking of the datatype of what you are traversing over.

For example, I could write out:

Tree = (Cons LeftNode RightNode)
     | Number

With that in mind its much easier to see that car and cdr will directly access your children.

(car (Cons LeftNode RightNode)) => LeftNode

(cdr (Cons LeftNode RightNode)) => RightNode

And obviously car and cdr of a number is going to be an error.

From here its fairly obvious how to define your depth function

(define (depth tree)
   (cond
      [(pair? tree)
       (+ 1 (max (depth (car tree))
                 (depth (cdr tree))))]
      [else 0]))

Note here that I used pair? instead of empty?. If you really want to understand what's going on here I highly recommend you check out How To Design Programs, which takes you through the design recipe steps I'm using here in a much slower (and cleaner) way.

If you want you can even extend this idea to contain trees with 3 or 4 child nodes:

Tree = (Listof Tree Tree Tree)
     | (Listof Tree Tree Tree Tree)
     | Number

Given this, can you figure out a rough datatype for a tree with an arbitrary amount of sub-tree nodes?