Problem 1: Binary Trees: Flatten

Recall the data definition for binary trees:

A binary-tree is either:

• #f

• (make-bt val left right)
  where val is a number,
  and left and right are binary-trees.
  

• (define-struct bt (val left right))

Write a function flatten that returns a list of the values of all the nodes in the tree.

Here are some examples (be sure to use these as tests when developing your function):

(define n1 (make-bt 1 #f #f))
(define n2 (make-bt 2 #f #f))
(define n3 (make-bt 3 #f #f))
(define m12 (make-bt 12 n1 n2))
(define r123 (make-bt 123 m12 n3))

(flatten r123) should be (123 12 1 2 3)
;; Note: This is simply a sample output. Any order of the same
;; numbers would be acceptable.
(flatten n1) should be (1)

Adding Data

Add new binary tree nodes and modify as few existing nodes as possible to produce a binary tree with four nodes at depth 2.

Submit your revised set of tree definitions.

Template

Write the template that you will follow in constructing this function.

Contract & Purpose

Write the contract specifying the input/output types of flatten and the purpose statement specifying its behavior.

Implementation

Write the code to implement flatten. Confirm that it produces the desired behavior on both the original examples and your modified examples.