// D. Scott
// CCI - Problem 4.5
// Determine whether a binary tree is a binary search tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    public Node parent;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v, Node n) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = n;
    }
    
    public void addChild(Node c) {
            children.add(c);
    }
}
        

public static void main (String[] args) {
    
    // build tree
    Node root = new Node(8);

    Node n = new Node(5, root);
    root.addChild(n);
    
    n2 = new Node(16,root);
    root.addChild(n2);

    n3 = new Node(-6,n);
    n.addChild(n3);

    n4 = new Node(0,n3);
    n3.addChild(n4);
    
    n5 = new Node(12,n4);
    n4.addChild(n5);
    
    // display tree
    System.out.println("\t\t\t\t\t"+root.value);
    System.out.println("\n");
    System.out.println("\t\t\t\t"+root.children.get(0).value+"\t\t"+
                       root.children.get(1).value);
    System.out.println("\n");
    Node c = root.children.get(0);
    System.out.println("\t\t\t"+c.children.get(0).value);
    System.out.println("\n");
    Node d = c.children.get(0);
    System.out.println("\t\t"+d.children.get(0).value);
    Node e = d.children.get(0);
    System.out.println("\n");
    System.out.println("\t"+e.children.get(0).value);
    System.out.println("\n");
    
    int[] empty = new int[0];
    int[] iot = buildIOT(root,empty);
    
    boolean is_bst = true;
    System.out.println("In-order traversal for the tree: ");
    for (int i = 0; i < iot.length; i++) {
        System.out.print(iot[i] + " ");
    }
    for (int i = 0; i < iot.length-1; i++) {
        if (iot[i] > iot[i+1]) {
            is_bst = false;
            break;
        }
    }
    if (is_bst == true)
        System.out.println("\n\nThe tree is a binary search tree.");
    else
        System.out.println("\n\nThe tree is not a binary search tree.");
    
    return;
    
    
}


public int[] buildIOT(Node r, int[] iot) {

    if (r.children.size() > 0)
        iot = buildIOT(r.children.get(0),iot);
    int[] new_iot = new int[iot.length+1];
    int i = 0;
    for (i = 0; i < iot.length; i++)
        new_iot[i] = iot[i];
    new_iot[i] = r.value;
    iot = new_iot;
    
    if (r.children.size() > 1 && r.children.get(1).value > r.value)
        iot = buildIOT(r.children.get(1),iot);
        return iot;
    if (r.children.size() <= 1)
        return iot;
    if (r.children.get(1) == r.value) {
        new_iot = new int[iot.length+1];
        i = 0;
        for (i = 0; i < iot.length; i++)
            new_iot[i] = iot[i];
        new_iot[i] = r.value-1;
        iot = new_iot;
        return iot;
    }
    
}


// D. Scott
// CCI - Problem 4.5
// Determine whether a binary tree is a binary search tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    public Node parent;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v, Node n) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = n;
    }
    
    public void addChild(Node c) {
            children.add(c);
    }
}
        

public static void main (String[] args) {
    
    // build tree
    Node root = new Node(6);

    Node n = new Node(3, root);
    root.addChild(n);
    
    n2 = new Node(9,root);
    root.addChild(n2);

    n3 = new Node(1,n);
    n.addChild(n3);
    n6 = new Node(3,n);
    n.addChild(n6);

    n4 = new Node(0,n3);
    n3.addChild(n4);
    
    n5 = new Node(8,n2);
    n2.addChild(n5);
    n6 = new Node(13,n2);
    n2.addChild(n6);

    n7 = new Node(10,n6);
    n6.addChild(n7);
    n8 = new Node(15,n6);
    n6.addChild(n8);
    
    n9 = new Node(18,n8);
    n8.addChild(n9);

    
    // display tree
    System.out.println("\t\t\t\t\t"+root.value);
    System.out.println("\n");
    System.out.println("\t\t\t\t"+root.children.get(0).value+"\t\t"+
                       root.children.get(1).value);
    System.out.println("\n");
    Node c = root.children.get(0);
    Node d = root.children.get(1);
    System.out.println("\t\t\t"+c.children.get(0).value+"\t\t"+c.children.get(1).value
                       +"   "+d.children.get(0).value+"\t\t"+d.children.get(1).value);
    System.out.println("\n");
    Node e = c.children.get(0);
    Node f = d.children.get(1);
    System.out.println("\t\t"+e.children.get(0).value+"\t\t\t\t  "+f.children.get(0).value +
                      "\t     "+f.children.get(1).value);
    Node g = f.children.get(1);
    System.out.println("\n");
    System.out.println("\t\t\t\t\t\t\t  "+g.children.get(0).value);
    System.out.println("\n");
    
    int[] empty = new int[0];
    int[] iot = buildIOT(root,empty);
    
    boolean is_bst = true;
    System.out.println("In-order traversal for the tree: ");
    for (int i = 0; i < iot.length; i++) {
        System.out.print(iot[i] + " ");
    }
    for (int i = 0; i < iot.length-1; i++) {
        if (iot[i] > iot[i+1]) {
            is_bst = false;
            break;
        }
    }
    if (is_bst == true)
        System.out.println("\n\nThe tree is a binary search tree.");
    else
        System.out.println("\n\nThe tree is not a binary search tree.");
    
    return;
    
    
}


public int[] buildIOT(Node r, int[] iot) {

    if (r.children.size() > 0) {
        iot = buildIOT(r.children.get(0),iot);
    }
    int[] new_iot = new int[iot.length+1];
    int i = 0;
    for (i = 0; i < iot.length; i++)
        new_iot[i] = iot[i];
    new_iot[i] = r.value;
    iot = new_iot;
    
    if (r.children.size() > 1 && r.children.get(1).value > r.value) {
        iot = buildIOT(r.children.get(1),iot);
        return iot;
    }
    if (r.children.size() <= 1) {
        return iot;
    }
    if (r.children.get(1).value == r.value) {
        new_iot = new int[iot.length+1];
        i = 0;
        for (i = 0; i < iot.length; i++)
            new_iot[i] = iot[i];
        new_iot[i] = r.value-1;
        iot = new_iot;
        return iot;
    }
    
}


// D. Scott
// CCI - Problem 4.5
// Determine whether a binary tree is a binary search tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    public Node parent;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = null;
    }
    
    public Node(int v, Node n) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = n;
    }
    
    public void addChild(Node c) {
            children.add(c);
    }
}
        

public static void main (String[] args) {
    
    // build tree
    Node root = new Node(6);

    Node n = new Node(3, root);
    root.addChild(n);
    
    n2 = new Node(9,root);
    root.addChild(n2);

    n3 = new Node(1,n);
    n.addChild(n3);
    n6 = new Node(5,n);
    n.addChild(n6);

    n4 = new Node(0,n3);
    n3.addChild(n4);
    
    n5 = new Node(8,n2);
    n2.addChild(n5);
    n6 = new Node(13,n2);
    n2.addChild(n6);

    n7 = new Node(10,n6);
    n6.addChild(n7);
    n8 = new Node(15,n6);
    n6.addChild(n8);
    
    n9 = new Node(14,n8);
    n8.addChild(n9);

    
    // display tree
    System.out.println("\t\t\t\t\t"+root.value);
    System.out.println("\n");
    System.out.println("\t\t\t\t"+root.children.get(0).value+"\t\t"+
                       root.children.get(1).value);
    System.out.println("\n");
    Node c = root.children.get(0);
    Node d = root.children.get(1);
    System.out.println("\t\t\t"+c.children.get(0).value+"\t\t"+c.children.get(1).value
                       +"   "+d.children.get(0).value+"\t\t"+d.children.get(1).value);
    System.out.println("\n");
    Node e = c.children.get(0);
    Node f = d.children.get(1);
    System.out.println("\t\t"+e.children.get(0).value+"\t\t\t\t  "+f.children.get(0).value +
                      "\t     "+f.children.get(1).value);
    Node g = f.children.get(1);
    System.out.println("\n");
    System.out.println("\t\t\t\t\t\t\t  "+g.children.get(0).value);
    System.out.println("\n");
    
    
    int[] empty = new int[0];
    int[] iot = buildIOT(root,empty);
    
    boolean is_bst = true;
    System.out.println("In-order traversal for the tree: ");
    for (int i = 0; i < iot.length; i++) {
        System.out.print(iot[i] + " ");
    }
    for (int i = 0; i < iot.length-1; i++) {
        if (iot[i] > iot[i+1]) {
            is_bst = false;
            break;
        }
    }
    if (is_bst == true)
        System.out.println("\n\nThe tree is a binary search tree.");
    else
        System.out.println("\n\nThe tree is not a binary search tree.");
    
    return;
    
    
}


public int[] buildIOT(Node r, int[] iot) {

    if (r.children.size() > 0) {
        iot = buildIOT(r.children.get(0),iot);
    }
    int[] new_iot = new int[iot.length+1];
    int i = 0;
    for (i = 0; i < iot.length; i++)
        new_iot[i] = iot[i];
    new_iot[i] = r.value;
    iot = new_iot;
    
    if (r.children.size() > 1 && r.children.get(1).value > r.value) {
        // System.out.println("There is a right child and it satisfies conditions.");
        iot = buildIOT(r.children.get(1),iot);
        return iot;
    }
    if (r.children.size() <= 1) {
        return iot;
    }
    if (r.children.get(1).value == r.value) {
        // System.out.println("There is a right child and it is equal to its parent.");
        new_iot = new int[iot.length+1];
        i = 0;
        for (i = 0; i < iot.length; i++)
            new_iot[i] = iot[i];
        new_iot[i] = r.value-1;
        iot = new_iot;
        // System.out.println("Appended "+r.value-1+ " to the IOT.");
        return iot;
    }
    
}