CODEWITHSUNDEEP
treeschemeracketdepth
Ptechnic
Ptechnic

Reputation: 11

Racket Tree Depth function (tree recursion) (No Structure Nodes!)

I'm trying to write a procedure (depth tree) that takes a tree as input and return an integer indicating the maximum level of the tree using Racket/Scheme

Example:

(depth '()) => 0
(depth '(1 2 3)) => 1
(depth '(a (b (c (d))))) => 4
(depth '((((((0))))))) => 6

I can't use structures in doing this, so it makes it a much more complicated task for me. I've tried using car/cdr recursion + and to do this, but I can't quite get it right. Any advice would be much appreciated.

Upvotes: 0

Views: 657

Answers (2)

ad absurdum
ad absurdum

Reputation: 21323

An input is an atom or a pair; if the input is a pair then it may contain either atoms or more pairs. When the input is a pair, you should add 1 to the maximum nesting level of the sub-pairs. Otherwise the input is not a pair, and the maximum nesting level is 0. Note that in Racket, '() is not a pair?.

These observations lead to a very simple definition:

#lang racket

(define (max-depth xss)
  (if (pair? xss)
      (+ 1 (apply max (map max-depth xss)))
      0))

Here, (map max-depth xss) evaluates to a list of the maximum nesting levels of all sublists within xss. To find the maximum, apply is needed to apply max to the list of arguments. Since the sublists themselves are already nested one level deep, 1 is added to the maximum.

max-depth.rkt> (max-depth 'x)
0
max-depth.rkt> (max-depth '())
0
max-depth.rkt> (max-depth '(1 2 3))
1
max-depth.rkt> (max-depth '(a (b (c (d)))))
4
max-depth.rkt> (max-depth '((((((0)))))))
6
max-depth.rkt> (max-depth '(a b (c d (e f (g)) h) (i j) (k (l (m (n (o) p))) q) r))
6

Upvotes: 1

tf3
tf3

Reputation: 467

Here is what I came up for this problem:

  • If the input is not an empty list, then using map, we can (recursively) check the maximum depth of recursion for each element in the list, and choose from the list that the map outputs, the element which has the greatest maximum depth of recursion and add 1 to it.

  • else if the input is the empty list, we return 0.

The code:

(define (depth tree)
  (if (null? tree)
      0
      (max-items (map (lambda (x)
                        (cond ((not (pair? x)) 1)
                              (else (+ 1 (depth x))))) tree))))

(define (max-items items)
  (define (iter lst cur-max)
    (cond ((null? lst) cur-max)
          ((> (car lst) cur-max) (iter (cdr lst) (car lst)))
          (else (iter (cdr lst) cur-max))))
 (iter (cdr items) (car items)))

Upvotes: 0

Related Questions