// D. Scott
// CCI - Problem 4.4
// Determine whether a binary tree is balanced

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    public Node parent;
    public int height;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
        this.parent = null;
        this.height = 0;
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = null;
        this.height = 0;
    }
    
    public Node(int v, Node n) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = n;
        this.height = 0;
    }
    
    public void addChild(Node c) {
        if (this.children.size() == 0) {
            this.height = 1;
            children.add(c);
            Node p = this.parent;
            while (p != null) {
                p.height++;
                p = p.parent;
            }
        } else {
            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");
    
    boolean unb = checkBalance(root,0);
    
    if (unb == false)
        System.out.println("\nThe tree is unbalanced.");
    else
        System.out.println("\nThe tree is balanced.");
    
    return;
    
    
}


public static boolean checkBalance(Node r,int u) {
    if (u == 1) {
        return false;
    }
    System.out.println("Checking children of "+r.value);
    if (r != null) {
        if (r.children.size() == 0) {
            System.out.println("No children. Balanced.");
            return;
        }
        if (r.children.size() == 1) {
            System.out.println("One child.");
            if (r.children.get(0).height > 1) {
                System.out.println("Height of "+r.children.get(0).height);
                System.out.println("Unbalanced.");
                u = 1;
                checkBalance(r.children.get(0),u);
                return;
            }
            else {
                System.out.println("Height of "+r.children.get(0).height);
                System.out.println("Balanced.");
                checkBalance(r.children.get(0),u);
                return;
            }
        }
        if (Math.abs(r.children.get(0).height - r.children.get(1).height) > 1) {
            System.out.println("Two children.");
            System.out.println("Height of child 1: "+r.children.get(0).height);
            System.out.println("Height of child 2: "+r.children.get(1).height);
            System.out.println("Unbalanced.");
            u = 1;
        } else {
            System.out.println("Two children.");
            System.out.println("Height of child 1: "+r.children.get(0).height);
            System.out.println("Height of child 2: "+r.children.get(1).height);
            System.out.println("Balanced.");            
        }
        checkBalance(r.children.get(0),u);
        checkBalance(r.children.get(1),u);
        if (u != 1)
            return true;
    }
}

import java.util.LinkedList;

class Node {
    public int value;
    LinkedList<Node> children;
    public Node parent;
    public int height;
    
    public Node() {
        this.value = 0;
        children = new LinkedList<Node>();
        this.parent = null;
        this.height = 0;
    }
    
    public Node(int v) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = null;
        this.height = 0;
    }
    
    public Node(int v, Node n) {
        this.value = v;
        children = new LinkedList<Node>();
        this.parent = n;
        this.height = 0;
    }
    
    public void addChild(Node c) {
        if (this.children.size() == 0) {
            this.height = 1;
            children.add(c);
            Node p = this.parent;
            while (p != null) {
                p.height++;
                p = p.parent;
            }
        } else {
            children.add(c);
        }
    }
}
        

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

    Node n = new Node(-2, root);
    root.addChild(n);
    
    n2 = new Node(-8,root);
    root.addChild(n2);

    n3 = new Node(5,n2);
    n2.addChild(n3);

    n4 = new Node(12,n2);
    n2.addChild(n4);
    
    // 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(1);
    System.out.println("\t\t\t\t\t"+c.children.get(0).value+"\t\t"+c.children.get(1).value);
    System.out.println("\n");
    
    boolean unb = checkBalance(root,0);
    
    if (unb == false)
        System.out.println("\nThe tree is unbalanced.");
    else
        System.out.println("\nThe tree is balanced.");
    
    return;
    
    
}


public static boolean checkBalance(Node r,int u) {
    if (u == 1) {
        return false;
    }
    System.out.println("Checking children of "+r.value);
    if (r != null) {
        if (r.children.size() == 0) {
            System.out.println("No children. Balanced.");
            return;
        }
        if (r.children.size() == 1) {
            System.out.println("One child.");
            if (r.children.get(0).height > 1) {
                System.out.println("Height of "+r.children.get(0).height);
                System.out.println("Unbalanced.");
                u = 1;
                checkBalance(r.children.get(0),u);
                return;
            }
            else {
                System.out.println("Height of "+r.children.get(0).height);
                System.out.println("Balanced.");
                checkBalance(r.children.get(0),u);
                return;
            }
        }
        if (Math.abs(r.children.get(0).height - r.children.get(1).height) > 1) {
            System.out.println("Two children.");
            System.out.println("Height of child 1: "+r.children.get(0).height);
            System.out.println("Height of child 2: "+r.children.get(1).height);
            System.out.println("Unbalanced.");
            u = 1;
        } else {
            System.out.println("Two children.");
            System.out.println("Height of child 1: "+r.children.get(0).height);
            System.out.println("Height of child 2: "+r.children.get(1).height);
            System.out.println("Balanced.");            
        }
        checkBalance(r.children.get(0),u);
        checkBalance(r.children.get(1),u);
        if (u != 1)
            return true;
    }
}