CoinProblem.java

import java.util.*;

public class CoinProblem
{

    LinkedList helper = new LinkedList();
    static int midway = 0;
    static BinaryTree tree = new BinaryTree();

    public CoinProblem()
    {
        // initialise instance variables
        int[] nums = {1,2,5,10,20,50,100,500,1000};

        Scanner sc = new Scanner(System.in);

        midway = (nums.length-1)/2;
        BinaryNode root = new BinaryNode(nums[midway]);
        tree.root = root;
        in(nums,0,nums.length-1,root);
        //tree.showValues(root);
        while(true){
            System.out.println("Enter dollar value: ");
            int dollars = sc.nextInt();
            System.out.println(change(tree, dollars));
        }
    }

    public static ArrayList<Integer> change (BinaryTree tree, int dollars){
        int remaining = dollars;

        ArrayList<Integer> list = new ArrayList<Integer>();

        while(remaining!=0){
            int change = floor(tree.root, remaining);
            list.add(change);
            remaining -= change;
        }

        return list;
    }

    static int floor(BinaryNode root, int key) 
    { 
        BinaryNode currNode = root;
        BinaryNode prev = null; 
        while (currNode != null) 
        { 
            if (currNode.data <= key) 
            { 
                prev = currNode; 
                currNode = currNode.right; 
            } 
            else
                currNode = currNode.left; 
        } 
        if (prev != null) 
            return prev.data; 
        return -1; 
    } 

    public static void in(int[] arr, int low, int high, BinaryNode node) {
        // check if low is smaller than high, if not then the array is sorted
        int m = low + (high-low)/2;
        if (m!=midway){
            tree.insert(node, arr[m]);
        }

        if(low < high){
            in(arr,m+1,high,node);
            in(arr,low,m,node);
        }
    }
}