CareerCup

#include<conio.h>
main{
}

import java.util.Arrays;
import java.util.Iterator;
import java.util.Vector;

/**
 *
 * @author Uday Kandpal
 */

/*
 * An interface for an sorted binary tree.
 * 
 * The interface provides methods for inserting values, checking if certain values are contained and iterating over the elements.
 * Note: Implementing classes should provide an iterator that traverse the inserted object in the sorted order.
 */
interface IBinTree<V extends Comparable<V>> extends Iterable<V> {
    /*
     * Insert an object into the binary tree. Note: The tree should be sorted, inserting the same object twice is allowed but the insert is expected to be stable.
     */

    void insert(V obj);
    /*
     * Batch-insert multiple elements.
     */

    void insert(Vector<V> vec);
    /*
     * Check if the object is already in the tree. Return true if it is, false otherwise. 
     */

    boolean contains(V obj);
}

public class BinaryTree<V extends Comparable<V>> implements IBinTree<V> {

    V value = null;
    BinaryTree<V> left = null;
    BinaryTree<V> right = null;

    private Vector<V> preOrder() {
        Vector<V> vector = new Vector();
        if (left != null) {
            vector.addAll(left.preOrder());
        }
        vector.add(value);
        if (right != null) {
            vector.addAll(right.preOrder());
        }
        return vector;
    }

    @Override
    public void insert(V obj) {
        if (value == null) {
            value = obj;
        } else if (value.compareTo(obj) == 1) {
            if (left == null) {
                left = new BinaryTree<>();
            }
            left.insert(obj);
        } else {
            if (right == null) {
                right = new BinaryTree<>();
            }
            right.insert(obj);
        }
    }

    @Override
    public void insert(Vector<V> vec) {
        Iterator<V> it = vec.iterator();
        while (it.hasNext()) {
            insert(it.next());
        }
    }

    @Override
    public boolean contains(V obj) {
        if (value.compareTo(obj) == 0) {
            return true;
        } else if (value.compareTo(obj) == 1) {
            return (left != null && left.contains(obj));
        } else {
            return (right != null && right.contains(obj));
        }
    }

    @Override
    public Iterator<V> iterator() {
        return preOrder().iterator();
    }

    public static void main(String[] args) {
        BinaryTree<Integer> tree = new BinaryTree<>();
        Integer[] list = new Integer[]{5, 3, 2, 8, 1, 7, 4, 9};
        tree.insert(new Vector<>(Arrays.asList(list)));
        Iterator it = tree.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }

    }
}