Number of levels in a tree

An n-ary tree is memorised in the following way:

(node (list-subtree-1) (list-subtree-2) ...)

As an example, the tree

A
/ \
B C
/ \
D E

is represented as follows:
(A (B) (C (D) (E)))

Return the number of levels of a tree

The problem is that I am only allowed to use the following functions: null, car, cdr, equal, atom, numberp, cons, cadr, caddr, cond and arithmtic functions.
Could anyone give me a function to return the levels of that kind of tree?
It would be great if you could give me a code that does not use the setq function.
Thanks in advance!

Perhaps you'd like to look at these hints again. The problem isn't too hard.

the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment

If you know how to obtain a certain number using a certain form, why do you need to set a variable to it?

If needed, post whatever code you have so far and perhaps more hints will be forthcoming.

Minato wrote:the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment

You don't need to store it. Either the right subtree of a node is deeper, or the left one is. So return the greater of the two.

I did it,thanks for the hint Paul it helped a lot.And thanks to all of you too!

Paul Donnelly wrote:

Minato wrote:the problem is that i cannot use the setq function,and I can't figure out how to store the value of the deepest level found at a certain moment

You don't need to store it. Either the right subtree of a node is deeper, or the left one is. So return the greater of the two.

And how do you do that for an "n-ary" tree? The answer includes a little bit of consing and recursion.

I have other 2 examples for this problem and both werw bynary trees,so i did it for a bynary tree,I dont think it could be rezolved otherwise without usin set functions

If your function is recursive, walking both the car and cdr parts of a list, and uses > to decide which depth number to return (such as to a + function), than it will work on n-ary trees. If you post the function you wrote, I'll post one I wrote and we can comment on it. Car is the first item in a list, Cdr is the rest of the list, so by walking down both car and cdr with a recursive function, your code will traverse a branch with any number of leaves or sub-branches. Car bites off the first element of successively smaller cdr lists, thus consuming a starting point list/tree of any length and any depth. The advantage of recursion is that by specifying how to handle any intermediate and final base cases in a given set of data, a function that calls itself doesn't have to use the additional complicated and data structure specific loops and variables that an imperative function would have to use. Specify the base cases, traverse both car and cdr, and trees of any n-ary complexity can be handled.

this is my code:

(defun nivel (l k)
(cond
((null (cdr l)) k)
((> (nivel (cadr l) (+ k 1)) (nivel (caddr l) (+ k 1))) (nivel (cadr l) (+ k 1)))
(t (nivel (caddr l) (+ k 1) ) )
)
)

Congratulations on a valiant attempt that is almost there. Here are some observations:

CL-USER> (nivel '((a) b c) 0)
; Evaluation aborted.
CL-USER>
-returned 'b is not of type list'

CL-USER> (nivel '((a) (b) (c)) 0)
1
CL-USER>
-function requires all root level leaves to be lists.

CL-USER> (nivel '((a) (b (d)) (c)) 0)
2
-works for this particular tree

CL-USER> (nivel '((a) ((b) d) (c)) 0)
; Evaluation aborted.
'd is not of type list'

CL-USER> (nivel '((a (d)) (b) (c)) 0)
1
CL-USER>
-mises d sub-branch of first root leaf a


Here is the code I wrote, which is made a little different by using if, progn and listp instead of cond and atom; is also messy and probably has more code than needed, but it works:

(defun levelnum(x)
       (+ 0
       (if (atom x) 0
       (progn
       (+
(if                   
       (>
 (if (not (null (cdr x))) (+ 0 (levelnum (cdr x)))0)
(if (listp (car x))  (+ 1 (levelnum (car x )))0))
 (if (not (null (cdr x))) (+ 0 (levelnum (cdr x)))0)
(if (listp (car x))  (+ 1 (levelnum (car x ))) 0)))))))     

CL-USER> (levelnum '((a) b c) )
1

CL-USER> (levelnum '((a) (b) (c)))
1

CL-USER> (levelnum '((a) (b (d)) (c)) 0)
2

CL-USER> (levelnum '((a) ((b) d) (c)) )
2

CL-USER> (levelnum '((a (d)) (b) (c)) )
2
CL-USER>

Also, look at these comparisons:

CL-USER> (levelnum '((a) (b) (c) (d (e))))
2
CL-USER> (nivel '((a) (b) (c) (d (e))) 0)
1



CL-USER> (levelnum '((a) ((k (o (r))) (d) ) (c (n))) )
4
CL-USER> (nivel '((a) ((k (o (r))) (d) ) (c (n))) 0)
2

Do you see the differences in the code that caused these result differences?

yep,understood,thx

what about a function to return the maximum value of all the numerical atoms of a list, at any level,without using set functions,could anyone give me some hints?

Look at the levelnum code and think about how to change it.

never mind,i did it,thanks again

Minato wrote:this is my code:

(defun nivel (l k)
  (cond
    ((null (cdr l)) k)
    ((> (nivel (cadr l) (+ k 1))
        (nivel (caddr l) (+ k 1)))
     (nivel (cadr l) (+ k 1)))
    (t (nivel (caddr l) (+ k 1)))))

Formatted. You can use

 tags for that.