## Number of levels in a tree

Discussion of Common Lisp

### 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.
Minato

Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

### Re: Number of levels in a tree

Perhaps you'd like to look at these hints again. The problem isn't too hard.
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin

Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

### Re: Number of levels in a tree

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
Minato

Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

### Re: Number of levels in a tree

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.
methusala

Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

### Re: Number of levels in a tree

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.
Paul Donnelly

Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

### Re: Number of levels in a tree

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

Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

### Re: Number of levels in a tree

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.
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin

Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

### Re: Number of levels in a tree

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
Minato

Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

### Re: Number of levels in a tree

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.
methusala

Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

### Re: Number of levels in a tree

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) ) )
)
)
Minato

Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Next