Binary Trees In Scheme (Module Language)

Homework help regarding an efficient binary tree function

Page 1 of 1

1 Replies - 9931 Views - Last Post: 20 May 2009 - 05:49 AM

#1 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Binary Trees In Scheme (Module Language)

Posted 19 May 2009 - 08:49 AM

Hello everyone,

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,

Zach

This post has been edited by Nizbel99: 19 May 2009 - 09:18 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Trees In Scheme (Module Language)

#2 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: Binary Trees In Scheme (Module Language)

Posted 20 May 2009 - 05:49 AM

I figured it out :)

For those who want to see my solution here it is :) (I got it to run a O(n) efficientcy :))


#lang scheme
(provide get-level make-person)

;;A binary tree is either empty, or has the follow definition: 
;;(make-node name left right), where name is a string, and 
;;where left and right are binary trees. 
(define-struct node (val left right))

;;Contract: get-level: BT num -> (listof string)
;;Purpose: To return a list of the values of the nodes on a given level. 
;;Examples:
;;(check-expect (get-level (make-node "Zach" empty empty) 0) (list "Zach"))
;;(check-expect (get-level (make-node "Zach" empty empty) 1) empty)

;;Body:
(define (get-level root lev)
 ;;Contract: get-helper: BT num (listof string) -> (listof string)
 ;;Purpose: To help create a list of the values of nodes on a given level.
 ;;Examples:
 ;;(check-expect (get-helper (make-node "Zach" empty empty) 0 empty) (list "Zach"))
 ;;(check-expect (get-helper (make-node "Zach" empty empty) 1 empty) empty)
  
 ;;Body:
  (local [(define (get-helper root lev acc)
			(cond
			  [(empty? root) acc]
			  [(= lev 0) (cons (node-val root) acc)]
			  [else
			  ;;Local constants.
			   (local [(define right-acc (get-helper (node-right root) (sub1 lev) acc))
					   (define left-acc (get-helper (node-left root) (sub1 lev) right-acc))]
				 left-acc)]))]
	(get-helper root lev empty)))



It uses 2 local accumulators to keep track of the nodes it needs to output in the list.
Enjoy - Zach
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1