# 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.

s.danicic@gold.ac.uk
Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2015-09-04