Page 1 of 2

Number of levels in a tree

Posted: Mon Nov 09, 2009 7:10 am
by Minato
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!

Re: Number of levels in a tree

Posted: Mon Nov 09, 2009 9:51 am
by Harleqin
Perhaps you'd like to look at these hints again. The problem isn't too hard.

Re: Number of levels in a tree

Posted: Mon Nov 09, 2009 11:58 am
by Minato
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

Re: Number of levels in a tree

Posted: Mon Nov 09, 2009 8:58 pm
by methusala
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.

Re: Number of levels in a tree

Posted: Mon Nov 09, 2009 11:12 pm
by Paul Donnelly
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.

Re: Number of levels in a tree

Posted: Tue Nov 10, 2009 2:02 am
by Minato
I did it,thanks for the hint Paul it helped a lot.And thanks to all of you too!

Re: Number of levels in a tree

Posted: Tue Nov 10, 2009 5:05 am
by Harleqin
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.

Re: Number of levels in a tree

Posted: Tue Nov 10, 2009 8:29 am
by Minato
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

Re: Number of levels in a tree

Posted: Tue Nov 10, 2009 11:28 am
by methusala
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.

Re: Number of levels in a tree

Posted: Tue Nov 10, 2009 12:29 pm
by Minato
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) ) )
)
)