Simply Scheme tree depth count

Question

I am working on question 18.3 in the Simply Scheme program (questions at bottom of page): https://people.eecs.berkeley.edu/~bh/ssch18/trees.html The problem is to write depth, a procedure that returns the number of nodes in the longest branch of a tree. So far I have written:

(define (depth-count node)
    (cond ((null? (children node))
     1)
    (else
     (reduce + (depth-count (children node)))))

So I have the base case as a 'leaf' node - no children. I want to + 1 for each parent node to a leaf, then compare nodes at the same depth and take the node with the max from each level. I am expecting to write more cond clauses which will choose one branch (max node) over another. I want the recursive case to be a list that I can count...that's where I think I am stuck. Am I going about this the right way? Any suggestions much appreciated.

Óscar López Óscar López · Accepted Answer · 2016-07-27T00:11:47

You're counting the number of nodes, not finding the longest branch - which is the same as finding the height of the tree. For that, you want to recursively find the maximum depth of the tree for each node. Something like this:

(define (depth-count node)
  (cond ((null? (children node)) 1) ; base case: if node is a leaf
        (else                       ; otherwise node has children
         (add1                                          ; add one
          (apply max                                    ; to the maximum of
                 (map depth-count (children node))))))) ; the recursive call

For example, if we use the above procedure with the world-tree defined in the given link, we obtain this:

(depth-count world-tree)
=> 4

Simply Scheme tree depth count

1 Answers