// D. Scott
// CCI - Problem 4.8
// Find the common ancestor of two given nodes in a binary tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
    }
        
    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.addChild(n);
    
    n2 = new Node(9);
    root.addChild(n2);

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

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

    n7 = new Node(10);
    n6.addChild(n7);
    n8 = new Node(15);
    n6.addChild(n8);
    
    n9 = new Node(14);
    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[] param = new int[6];
    
    System.out.println("Nodes: p = "+n4.value+" , q = "+n10.value+"\n");
    param = inOrder(root,n4,n10,root,0,0,0,param);
    return;
}


/* in-order traversal, returns 6-slot array which holds values of:
 * [0]: status of p_f, [1]: status of q_f, [2]: status of r_f
 * [3]: 0 for left subtree, 1 for right subtree
 * [4]: common ancestor value, [5]: common ancestor found status
 */
public int[] inOrder(Node n, Node p, Node q, Node r,
                     int p_f, int q_f, int r_f, int[] param) {
    // root found
    if (param[0] == 1 && param[2] == 1 && param[1] == 0) {
        param[4] = n.value;
        param[5] = 1;
        System.out.println("\nCommon ancestor is "+r.value);
        return param;
    }
    // root in left subtree
    if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
        System.out.println("Common ancestor is in left subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(0);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    // root in right subtree
    if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    if (n == null)
        return param;

    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    
    // left traversal
    if (n.children.size() > 0)
        param = inOrder(n.children.get(0),p,q,r,param[0],param[1],param[2],param);
    else {
        if (n == p) {
            System.out.println("Node "+p.value+" found.");
            param[0] = 1;

            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        else if (n == q) {
            System.out.println("Node "+q.value+" found.");
            param[1] = 1;
            
            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        return param;
    }
    if (param[5] == 1)
        return param;
    System.out.println("Current node in tree: "+n.value);
    
    // root check
    
    if (n == p) {
        System.out.println("Node "+p.value + " found.");
        param[0] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            parma[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }

    if (n == q) {
        System.out.println("Node "+q.value + " found.");
        param[1] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }
    if (param[5] == 1)
        return param;
    if (n == r) {
        System.out.println("Root "+r.value + " found.");
        param[2] = 1;
    }
    
    // right traversal
    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    if (n.children.size() > 1)
        param = inOrder(n.children.get(1),p,q,r,param[0],param[1],param[2],param);
    else
        return param;
    
    
}

// D. Scott
// CCI - Problem 4.8
// Find the common ancestor of two given nodes in a binary tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
    }
        
    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.addChild(n);
    
    n2 = new Node(9);
    root.addChild(n2);

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

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

    n7 = new Node(10);
    n6.addChild(n7);
    n8 = new Node(15);
    n6.addChild(n8);
    
    n9 = new Node(14);
    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[] param = new int[6];
    
    System.out.println("Nodes: p = "+n5.value+" , q = "+n7.value+"\n");
    param = inOrder(root,n5,n7,root,0,0,0,param);
    return;
}


/* in-order traversal, returns 6-slot array which holds values of:
 * [0]: status of p_f, [1]: status of q_f, [2]: status of r_f
 * [3]: 0 for left subtree, 1 for right subtree
 * [4]: common ancestor value, [5]: common ancestor found status
 */
public int[] inOrder(Node n, Node p, Node q, Node r,
                     int p_f, int q_f, int r_f, int[] param) {
    // root found
    if (param[0] == 1 && param[2] == 1 && param[1] == 0) {
        param[4] = n.value;
        param[5] = 1;
        System.out.println("\nCommon ancestor is "+r.value);
        return param;
    }
    // root in left subtree
    if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
        System.out.println("Common ancestor is in left subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(0);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    // root in right subtree
    if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    if (n == null)
        return param;

    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    
    // left traversal
    if (n.children.size() > 0)
        param = inOrder(n.children.get(0),p,q,r,param[0],param[1],param[2],param);
    else {
        if (n == p) {
            System.out.println("Node "+p.value+" found.");
            param[0] = 1;

            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        else if (n == q) {
            System.out.println("Node "+q.value+" found.");
            param[1] = 1;
            
            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        return param;
    }
    if (param[5] == 1)
        return param;
    System.out.println("Current node in tree: "+n.value);
    
    // root check
    
    if (n == p) {
        System.out.println("Node "+p.value + " found.");
        param[0] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            parma[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }

    if (n == q) {
        System.out.println("Node "+q.value + " found.");
        param[1] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }
    if (param[5] == 1)
        return param;
    if (n == r) {
        System.out.println("Root "+r.value + " found.");
        param[2] = 1;
    }
    
    // right traversal
    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    if (n.children.size() > 1)
        param = inOrder(n.children.get(1),p,q,r,param[0],param[1],param[2],param);
    else
        return param;
    
    
}

// D. Scott
// CCI - Problem 4.8
// Find the common ancestor of two given nodes in a binary tree

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
    }
        
    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.addChild(n);
    
    n2 = new Node(9);
    root.addChild(n2);

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

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

    n7 = new Node(10);
    n6.addChild(n7);
    n8 = new Node(15);
    n6.addChild(n8);
    
    n9 = new Node(14);
    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[] param = new int[6];
    
    System.out.println("Nodes: p = "+n10.value+" , q = "+n8.value+"\n");
    param = inOrder(root,n10,n8,root,0,0,0,param);
    return;
}


/* in-order traversal, returns 6-slot array which holds values of:
 * [0]: status of p_f, [1]: status of q_f, [2]: status of r_f
 * [3]: 0 for left subtree, 1 for right subtree
 * [4]: common ancestor value, [5]: common ancestor found status
 */
public int[] inOrder(Node n, Node p, Node q, Node r,
                     int p_f, int q_f, int r_f, int[] param) {
    // root found
    if (param[0] == 1 && param[2] == 1 && param[1] == 0) {
        param[4] = n.value;
        param[5] = 1;
        System.out.println("\nCommon ancestor is "+r.value);
        return param;
    }
    // root in left subtree
    if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
        System.out.println("Common ancestor is in left subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(0);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    // root in right subtree
    if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
    }
    if (n == null)
        return param;

    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    
    // left traversal
    if (n.children.size() > 0)
        param = inOrder(n.children.get(0),p,q,r,param[0],param[1],param[2],param);
    else {
        if (n == p) {
            System.out.println("Node "+p.value+" found.");
            param[0] = 1;

            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        else if (n == q) {
            System.out.println("Node "+q.value+" found.");
            param[1] = 1;
            
            // value check after node found - proceed with next traversal?
            if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
                System.out.println("Common ancestor is in left subtree.");
                System.out.println("\n\nStarting new traversal...");
                r = r.children.get(0);
                n = r;
                param[0] = 0;
                param[1] = 0;
                param[2] = 0;
                param[3] = 0;
                param[4] = 0;
                param[5] = 0;
                param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
                return param;
            }
            if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
            System.out.println("Common ancestor is in right subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(1);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
            }
        }
        return param;
    }
    if (param[5] == 1)
        return param;
    System.out.println("Current node in tree: "+n.value);
    
    // root check
    
    if (n == p) {
        System.out.println("Node "+p.value + " found.");
        param[0] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            parma[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }

    if (n == q) {
        System.out.println("Node "+q.value + " found.");
        param[1] = 1;
        
        // value check after node found - proceed with next traversal?
        if (param[0] == 1 && param[1] == 1 && param[2] == 0) {
            System.out.println("Common ancestor is in left subtree.");
            System.out.println("\n\nStarting new traversal...");
            r = r.children.get(0);
            n = r;
            param[0] = 0;
            param[1] = 0;
            param[2] = 0;
            param[3] = 0;
            param[4] = 0;
            param[5] = 0;
            param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
            return param;
        }
        if (param[0] == 0 && param[1] == 0 && param[2] == 1) {
        System.out.println("Common ancestor is in right subtree.");
        System.out.println("\n\nStarting new traversal...");
        r = r.children.get(1);
        n = r;
        param[0] = 0;
        param[1] = 0;
        param[2] = 0;
        param[3] = 0;
        param[4] = 0;
        param[5] = 0;
        param = inOrder(n,p,q,r,param[0],param[1],param[2],param);
        return param;
        }
    }
    if (param[5] == 1)
        return param;
    if (n == r) {
        System.out.println("Root "+r.value + " found.");
        param[2] = 1;
    }
    
    // right traversal
    System.out.println("Current node in tree: "+n.value+" with "+n.children.size()+ " children.");
    if (n.children.size() > 1)
        param = inOrder(n.children.get(1),p,q,r,param[0],param[1],param[2],param);
    else
        return param;
    
    
}