public class IsTreeBalanced {

	public static void main(String[] args) {

		// build a tree with Nodes...root is root Node
		isBalanced(root);

	}

	public static int getHeight(Node root) {

		// base case, bottom of sub tree
		if (root == null) {
			return 0;
		}

		// get height of left subtree, and check if it is balanced
		int heightLeft = getHeight(root.left);
		if (heightLeft == -1) {
			return -1;
		}

		// get height of right subtree, and check if it is balanced
		int heightRight = getHeight(root.right);
		if (heightRight == -1) {
			return -1;
		}

		// get difference between left and right, if > 1 they are unbalanced
		int heightDiff = Math.abs(heightRight - heightLeft);
		if (heightDiff > 1)
			return -1;
		else
			return Math.max(heightLeft, heightRight) + 1;
	}

	public static void isBalanced(Node root) {

		if (getHeight(root) == -1) {
			System.out.println("Tree not balanced");
			return;
		} else {
			System.out.println("Tree IS balanced!");
		}
	}



}

class Node {

	int data;
	public Node left;
	public Node right;

	public Node(int n) {
		data = n;
		left = null;
		right = null;
	}
}