Homework #3

Important: All functions in this homework should be purely functional. Your solutions should not use ML's imperative features, references, side-effecting primitives, etc.

Part A (Warm-Up):

1. before: Write a function before with signature 'a list * 'a -> 'a list such that before(l, x) returns the list of all elements that occur immediately before x in l For instance:
   • before([5;3;2;4;1;3;6;2;3],3) returns [5;1;2]
   • before([5;3;2;4;1;3;6;2;3],2) returns [3;6]
   • before([5;3;2;4;1;3;6;2;3],1) returns [4]
   • before([5;3;2;4;1;3;6;2;3],5) returns []
   • before([5;3;2;4;1;3;6;2;3],8) returns []

2. order: Write a function order with signature 'a list * 'a * 'a -> bool such that order(l, x, y) returns true if and only if elements x and y occur in list l such that x occurs before y. For instance:
   • order([1;3;2;4],1,2) order([1;3;2;4],3,4) order([1;3;2;4],3,2) order([1;3;2;4],1,4) all return true.
   • order([1;3;2;4],4,3) order([1;3;2;4],1,5) order([1;3;2;4],1,1) all return false.

3. split: Write a function split with signature 'a list * 'a -> 'a list * 'a list such that split(l, x) returns a pair of lists (p, s) such that p is the list of all elements that occur before x in l, and s is the list of all elements that occur after x in l. The order of elements in p and s are same as that in l. If there is no element x in l, then the function should raise exception NoneSuch. For instance:
   • split([1;2;3;4], 1) should return ([], [2;3;4])
   • split([1;2;3;4], 2) should return ([1], [3;4])
   • split([1;2;3;4], 3) should return ([1;2], [4])
   • split([1;2;3;4], 4) should return ([1;2;3], [])
   • split([1;2;3;4], 5) should raise NoneSuch.

   Part B (Trees):

   For the following four questions, consider using OCAML datastructure, defined by

   type 'a tree = Node of 'a * 'a tree * 'a tree | Empty;;

   to represent binary trees.

   (a)	(b)	(c)

   For instance,

   • Tree (a) in the picture above is represented by term Node(5, Node(3, Node(1, Empty, Empty), Node(2, Empty, Empty)), Node(13, Empty, Node(8, Empty, Empty))).
   • Tree (b) in the picture above is represented by term Node(8, Node(2, Node(1, Empty, Empty), Node(5, Node(3, Empty, Empty), Empty)), Node(13, Empty, Node(21, Empty, Empty))).
   • Tree (c) in the picture above is represented by term Node(5, Node(2, Node(1, Empty, Empty), Node(3, Empty, Empty)), Node(13, Node(8, Empty, Empty), Empty)).

4. isBalanced: Write a function isBalanced with signature 'a tree -> bool that returns true if and only if t is a binary tree that is height-balanced: i.e., the lengths of the longest root-to-leaf path and the shortest root-to-leaf path differ by at most one.

   For example, trees (a) and (c) in the picture above are balanced.

5. isOrdered: Write a function isOrdered with signature 'a tree -> bool that returns true if and only if an in-order traversal of t spells out an increasing sequence of values. For this part, you may assume that all values in t are comparable with "<".
   Note: In-order traversal of a tree traverses, at each level, the left subtree, the root, and then the right subtree.

   For example, trees (b) and (c) in the above picture are ordered.

6. buildBalanced: Write a function buildBalanced with 'a list -> 'a tree such that buildBalanced(l) results in a balanced tree t such that an in-order traversal of t spells out l.

   For example, buildBalanced([1;2;3;5;8;13]) can give the tree (c) in the picture above, as one possible answer. (Other balanced trees may be possible as well; you can make that choice.)

7. postOrder: Write a function postOrder with signature 'a tree -> 'a list that returns a list l such that post-order traversal of t spells out l.
   Note: Post-order traversal of a tree traverses, the left subtree, the right subtree, and then the root.

   For example,

   • postOrder on example tree (a) should return [1;2;3;8;13;5]
   • postOrder on example tree (b) should return [1;3;5;2;21;13;8]
   • postOrder on example tree (b) should return [1;3;2;8;13;5]

   Note: For full credit in this problem, your solution should work for trees with millions of nodes. As a point of reference, there are solutions where trees with 100,000 nodes (irrespective of skew and balance) can be processed in less than a second.

Grading:

Submission:

The file must be named hw3.ml

Errata:

1. None so far.