// dsaII_17_7_skeleton.java SJ

/**
  * 7. Recap from DSA I course: Write an algorithm that collects all leaf nodes
  * of a binary tree (i.e., those nodes that have no children). Algorithm gets
  * as a parameter a binary tree, and returns a set of binary tree nodes. What
  * is the time complexity of your algorithm? Hint: recursion.
  **/

import fi.joensuu.cs.tra.*;

import java.util.Set;
import java.util.HashSet;
import java.util.Random;

public class dsaII_17_7_skeleton {

	public static void main(String[] args) {

		BTree<Integer> tree = new BTree<Integer>();

        // size of tree
		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);

		System.out.println("Into tree:");
		Random r = new Random(42);
		Integer x = new Integer(0);
		for (int i = 0; i < N; i++) {
			x = r.nextInt(N*2);
			System.out.print(x + " ");
			inorderInsert(tree, x);
		}
		System.out.println();

		System.out.println("Leaf nodes:");
		System.out.println(leafNodes(tree));

        // separately a fixed example tree
        tree = exampleBTree();

		System.out.println("Leaf nodes:");
		System.out.println(leafNodes(tree));

        
		
	} // main()




    /**
      * Find all leaf nodes.
      * @param T binary tree.
      * @return set of leaf nodes
      **/
    public static Set<BTreeNode> leafNodes(BTree T) {

        Set<BTreeNode> S = new HashSet<BTreeNode>();

        // TODO

        return S;
    }

    // actual recursive method
    private static void leafNodes(BTreeNode n, Set<BTreeNode> S) {

        // TODO

    }

	

    // helper methods
	
    public static BTree<Integer> exampleBTree() {

        BTree<Integer> T = new BTree<Integer>();

        // root
        T.setRoot(new BTreeNode<Integer>(10));

        BTreeNode<Integer> n = T.getRoot();

        // root children
        n.setLeftChild(new BTreeNode<Integer>(5));
        n.setRightChild(new BTreeNode<Integer>(15));

        // left branch
        BTreeNode<Integer> l = n.getLeftChild();

        l.setLeftChild(new BTreeNode<Integer>(3));
        l.setRightChild(new BTreeNode<Integer>(8));

        l.getLeftChild().setRightChild(new BTreeNode<Integer>(4));

        // right branch
        l = n.getRightChild();

        l.setLeftChild(new BTreeNode<Integer>(12));
        l.setRightChild(new BTreeNode<Integer>(18));

        l.getLeftChild().setLeftChild(new BTreeNode<Integer>(11));
        l.getLeftChild().setRightChild(new BTreeNode<Integer>(13));


        System.out.println("                 ");
        System.out.println("       10        ");
        System.out.println("    __/  \\__     ");
        System.out.println("   5        15   ");
        System.out.println("  / \\      /  \\  ");
        System.out.println(" 3   8   12    18");
        System.out.println("  \\      /\\      ");
        System.out.println("   4    11 13    ");
        System.out.println("                 ");

        return T;

    } // exampleBTree()

	public static <E extends Comparable<? super E>> 
						boolean inorderInsert(BTree<E> T, E x) {
		BTreeNode<E> n = T.getRoot();
		if (n == null) {
			T.setRoot(new BTreeNode<E>(x));
			return true;
		}

		while (true) {

			if (x.compareTo(n.getElement()) == 0)
				return false;
			
			else if (x.compareTo(n.getElement()) < 0) {
				if (n.getLeftChild() == null) {
					n.setLeftChild(new BTreeNode<E>(x));
					return true;
				} else
					n = n.getLeftChild();
			} else {
				if (n.getRightChild() == null) {
					n.setRightChild(new BTreeNode<E>(x));
					return true;
				} else
					n = n.getRightChild();
			}
		} // while

	} // inorderInsert()
	
}   // class