Solved–Homework 2– Solution

Description

0. (13 pts) Write a recursive Scheme function (subst x y L), which returns a list identical to L except that every occurrence of x has been replaced with y. The following example illustrates the use of this function:

0. • • (subst ‘c ‘k ‘(c o c o n u t))

(k o k o n u t)

2. (13 pts) Write a recursive Scheme function (all-different? L), which determines whether all elements of list L are distinct (that is, not equal?). The following example illustrates the use of this function:

2. • (all-different? ‘(3 7 2 7))

#f

2. (60 pts) Consider an implementation of binary trees with Scheme lists, as in the following example:

(define T			13
‘(13
(5		5		22
(1 () ())
(8 ()	1	8
(9 () ())))			17	25
(22
(17 () ())			9
(25 () ()))))

Before proceeding, it may be useful to define three auxiliary functions (left T), (right T) and (val T) which return the left subtree, the right subtree, and the value in the root of tree T, respectively.

1. (15 pts) Write a recursive function (n-nodes T), which returns the number of nodes in the tree T. The following example illustrates the use of this function:

> (n-nodes T)

8

2. (15 pts) Write a recursive function (n-leaves T), which returns the number of leaves in the tree T. The following example illustrates the use of this function:

> (n-leaves T)

4

3. (15 pts) The height of a tree is defined as the maximum number of nodes on a path from the root to a leaf. Write a recursive function (height T), which returns the height of the tree T. The following example illustrates the use of this function:

> (height T)

4

4. (15 pts) Write a recursive function (postorder T), which returns the list of all elements in the tree T corresponding to a postorder traversal of the tree. The following example illustrates the use of this function:

> (postorder T)

(198517252213)

4. (14 pts) Write a recursive Scheme function (flatten L), which takes as arguments a list L (possibly containing sublists), and returns a list containing all elements in L and its sublists, but all at the same level. The following example illustrates the use of this function:

4. • (flatten ‘(1 (2 (3 4)) 5)) (12345)

4. (Extra Credit – 10 pts) A binary search tree is a binary tree for which the value in each node is greater than or equal to all values in its left subtree, and less than all values in its right subtree. The binary tree given as example in problem 3 also qualifies as a binary search tree. Using the same list representation, write a recursive function (member-bst? V T), which determines whether V appears as an element in the binary search tree T. Make sure you actually use binary search. The following example illustrates the use of this function:

4. • (member-bst? 17 T)

#t