Semester 2 Week 2 Binary Trees

1. Consider the Hope implementation of binary trees. Implement binary trees in Java.

   data binaryTree(alpha) == emptyTree ++ consbinaryTree(alpha # binaryTree(alpha) # binaryTree(alpha));
   
   root:binaryTree(alpha) -> alpha; 
   root(consbinaryTree(x,y,z)) <= x;
   
   left:binaryTree(alpha) -> binaryTree(alpha); 
   left(consbinaryTree(x,y,z)) <= y;
   
   right:binaryTree(alpha) -> binaryTree(alpha); 
   right(consbinaryTree(x,y,z)) <= z;
   
   isEmpty:binaryTree(alpha) ->bool; 
   isEmpty(emptyTree) <= true;
   isEmpty(consbinaryTree(x,y,z)) <= false;
   
   max:num # num -> num;
   max(x,y) <= if x>y then x else y;
   
   depth:binaryTree(alpha) -> num; 
   depth(emptyTree) <= 0;
   depth(consbinaryTree(x,y,z)) <= 1 + max(depth(y),depth(z));
   

   binaryTree.java emptyTree.java consbinaryTree.java

2. (Easy Assignment) Below is a Hope function make for converting a list of numbers into a binary search tree of numbers. Implement this as a static method in Java and write some Java to test your method.

   insert: num # binaryTree(num) -> binaryTree(num);
   insert (n, emptyTree) <= consbinaryTree(n,emptyTree,emptyTree);
   insert (n,consbinaryTree(roo,lef,rig)) <= if n < roo 
   					  then consbinaryTree(roo, insert(n,lef),rig)
                                             else consbinaryTree(roo, lef, insert(n,rig));
   Main-Class: hangmanGUI3
   make :list(num) -> binaryTree(num);
   make(nil) <= emptyTree;
   make(x::m) <=  insert(x,make(m));
   

3. (Hard Assignment) A balanced binary tree is either empty or a tree where the number of nodes in the left and right subtrees differs by at most one and the left and right subtrees are balanced.

   Write a method in Java which takes a list of numbers and produces a balanced binary search tree containing exactly those numbers.