// D. Scott
// CCI - Problem 4.6
// Find the successor to a given node in 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);
    n10 = 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"); 

    // test successors
    Node s1 = getSuccessor(n);
    Node s2 = getSuccessor(n8);
    Node s3 = getSuccessor(n6);
    Node s4 = getSuccessor(root);
    Node s5 = getSuccessor(n10);

    if (s1 != null) 
        System.out.println("Successor to node " + n.value + ": "+ s1.value);
    else
        System.out.println("Successor to node " + n.value + ": null");

    if (s2 != null) 
        System.out.println("Successor to node " + n8.value + ": "+ s2.value);
    else
        System.out.println("Successor to node " + n8.value + ": null");
    
    if (s3 != null) 
        System.out.println("Successor to node " + n6.value + ": "+ s3.value);
    else
        System.out.println("Successor to node " + n6.value + ": null");

    if (s4 != null) 
        System.out.println("Successor to node " + root.value + ": "+ s4.value);
    else
        System.out.println("Successor to node " + root.value + ": null");

    if (s5 != null) 
        System.out.println("Successor to node " + n10.value + ": "+ s5.value);
    else
        System.out.println("Successor to node " + n10.value + ": null");

    
}

public Node getSuccessor(Node r) {
    Node parent = r;
    
    while (parent.parent != null) {
        parent = parent.parent;
    }
    
    LinkedList<Node> iot = new LinkedList<>();
    LinkedList<Node> inOrder = buildIOT(parent,iot);
    
    // iterate through in-order traversal to node, return next one in list
    Iterator<Node> iterator = inOrder.iterator();
    boolean found = false;
    while (iterator.hasNext()) {
        Node s = iterator.next();
        if (s == r) {
            found = true;
            if (iterator.hasNext())
                return iterator.next();
            else
                return null;
        }
    }
    if (found == false) {
        return null;
    }
}

// build a linked list of nodes representing in-order traversal
public LinkedList<Node> buildIOT(Node r, LinkedList<Node> iot) {

    if (r.children.size() > 0)
        iot = buildIOT(r.children.get(0),iot);
    // add node to linked list for in-order traversal

    iot.add(r);
    
    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;
    
}