/* Test Whether or Not a Binary Tree is Balanced */
public class BalancedTree {
	public static int minDepth;
	public static int maxDepth;
	public static boolean notBalanced;
	public static void main(String[] args){
		runTests();
		return;
	}

	public static void runTests(){
		TreeNode one = new TreeNode(1);
		TreeNode two = new TreeNode(2);
		TreeNode three = new TreeNode(3);

		two.left = one;
		two.right = three;
		if(isBalanced(two)!=true)
			System.out.println("Failed Test One");
		two.left = three;
		two.right = null;
		one.left = two;
		if(isBalanced(one))
			System.out.println("Failed Test Two");
		if(isBalanced(two)!=true)
			System.out.println("Failed Test Three");
		if(isBalanced(three)!=true)
			System.out.println("Failed Test Four");
		System.out.println("Finished testing Blanced Tree");
		return;
	}

	public static boolean isBalanced(TreeNode root){
		minDepth=0;
		maxDepth=0;
		notBalanced=false;
		helper(root, 0);
		if(notBalanced) return false;
		return true;
	}

	public static void helper(TreeNode root, int accum){
		if((notBalanced)||(root==null)) return;

		/* We're at a leaf */
		else if((root.left==null)||(root.right==null)){
			if(minDepth==0) minDepth = accum+1;
			else minDepth = min(minDepth, accum+1);
			if(maxDepth==0) maxDepth = accum+1;
			else maxDepth = max(maxDepth, accum+1);
			if((maxDepth-minDepth)>=2) notBalanced=true;
		}
		helper(root.left, accum+1);
		helper(root.right, accum+1);
		return;
	}

	public static int min(int a, int b){
		if(a>b) return b;
		return a;
	}

	public static int max(int a, int b){
		if(a>b) return a;
		return b;
	}
	
}

/* Breaking Encapsulation for Simplicity */
class TreeNode {
	public int value;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(int val){
		this.value = val;
		this.left = null;
		this.right = null;
	}
}