I'm having an enourmous amount of trouble trying to devellop the following function. In scheme, we gave the following definition for a binary tree:
(define node (val left right))-> where val is a string, and where left and right are the left and right nodes in the binary tree. If there is no node at the given position, we use the keyword empty. So, for example, a binary tree with just the root node would be defined as
(make-node "Me" empty empty).
Ok, now that we have defined this, for class, we need to make a function that takes 2 arguments: a binary tree, and a number (the number is called the level). The function then has to return a list of values of all the nodes at the corresponding level (where level starts at 0). So for example:
(get-level (make-node "Nizbel99" empty (make-node "Test2" empty empty)) 1)would return
(list "Test2"). The list just contains strings of the node values at that given level.
Now, I have made a function that works as follows:
(define (get-level root lev) (cond [(empty? root) empty] [(= lev 0) (list (node-val root))] [else (append (get-level (node-left root) (sub1 lev)) (get-level (node-right root) (sub1 lev)))]))
This function gives the required results perfectly. However, here's the catch. For full marks the function must have a run time of BELOW O(n^2). I've e-mailed my teacher and she suggested using an accumulator. But I'm not sure as to what accumulate on. This is what I have so far:
(define (get-level root lev) (cond [(empty? root) empty] [(= lev 0) (list (node-val root))] [(and (empty? (node-left root)) (empty? (node-right root))) empty] [else (local [(define (get-lvl root lev acc) (cond [...]))])]))
I'm not really sure as to how I should approch the problem. Basically, since we need a function below order n^2, I can't use append, or other functions that have to traverse the accumulator or the tree more than once.
PS: Also, we can't use mutation - and again, this is done in the module language.
Any help would be great -> A sample solution, or an idea would be great. I've been trying to come up with a solution for the past 48 hours without luck - and I've looked online for something similar without luck either. So, like I said, any help would be much appreciated.
Thanks in advanced,
This post has been edited by Nizbel99: 19 May 2009 - 09:18 AM