import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


public class BTree {
    private int value;
    private BTree left;
    private BTree right;
    private BTree parent;

    public BTree() {
    }

    public BTree(int v) {
        this.value = v;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public static BTree createMinimalBT(BTree root, int[] array, int s, int e) {
        if (s >= 0 && e  k - 1)
            return k_smallest_element(root.left, k);
        else // ( i < k-1)
            return k_smallest_element(root.right, k - i - 1);
    }

    public static int counter = 0;
    public static void k_smallest_element1(BTree root, int k) {
        if (root == null) return;

        k_smallest_element1(root.left, k);

        if(++counter == k)       // count root node
            System.out.println("tree smallest: "+ root.value);

        k_smallest_element1(root.right, k);

    }

    public static void main(String[] args) {
        int[] a1 = new int[]{2, 3, 4, 5, 7, 9, 12, 13, 10, 18, 20};


        BTree t1 = new BTree();
        t1 = createMinimalBT(t1, a1, 0, a1.length - 1);
        System.out.println("tree height: " + height(t1));
        System.out.println("t3 binary tree width " + width(t1));
        System.out.println("tree size: " + treeSize(t1));
        System.out.println("tree 4 smallest: " + k_smallest_element(t1, 4).value);
        k_smallest_element1(t1,3);

        showByLevel(t1);


        int[] a2 = new int[]{1, 3, 5, 6, 9};
        Arrays.sort(a2);

        BTree t2 = new BTree();
        t2 = createMinimalBT(t2, a2, 0, a2.length - 1);
        System.out.println("tree height: " + height(t2));
        System.out.println("t3 binary tree width " + width(t2));
        showByLevel(t2);

        System.out.println(containTree(t1, t2));

        int p = 12, q = 18;
        BTree cr = commonRootTopDown(t1, p, q);
        System.out.println("top down common root: " + p + " and  " + q);
        if (cr != null && coverNode(t1, p) != null && coverNode(t1, q) != null)
            System.out.println(cr.value);

        p = 12;
        q = 13;
        BTree cr1 = commonRoot(t1, p, q);
        System.out.println("common root: " + p + " and  " + q);
        if (cr1 != null && coverNode(t1, p) != null && coverNode(t1, q) != null)
            System.out.println(cr1.value);

        int sum = 19;
        ArrayList result = findAllPathSum(t1, sum);
        System.out.println("find sum: " + sum);
        for (ArrayList l : result) {
            for (BTree n : l) {
                System.out.print(n.value + " ");
            }
            System.out.println();
        }

        BTree t3 = new BTree(10);
        insertNode(t3, 3);
        insertNode(t3, 7);
        insertNode(t3, 4);
        insertNode(t3, 5);
        insertNode(t3, 2);
        insertNode(t3, 1);
        insertNode(t3, 0);
        insertNode(t3, 15);
        insertNode(t3, 12);
        insertNode(t3, 18);
        insertNode(t3, 16);
        insertNode(t3, 20);

        System.out.println("t3 binary tree");
        System.out.println("t3 binary tree width " + width(t3));
        showByLevel(t3);

        int suc = 3;
        BTree nextNode = inorderSuc(t3, suc);
        System.out.println("t3 inorder successor " + suc);
        if (nextNode != null)
            System.out.println(nextNode.value);

        int suc2 = 3;
        BTree nextNode1 = postorderSuc(t3, suc2);
        System.out.println("t3 postorder successor " + suc2);
        if (nextNode1 != null)
            System.out.println(nextNode1.value);

        int suc3 = 0;
        BTree nextNode2 = preorderSuc(t3, suc3);
        System.out.println("t3 preorder successor " + suc3);
        if (nextNode2 != null)
            System.out.println(nextNode2.value);

    }

}