A binary tree is balanced if both its children are balanced and the difference between the heights of its children is at most 1./** * Definition for a binary tree node. */class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode parent;    TreeNode(int x) {        val = x;    }}public class isBalanced {    // first we will get the left height and right height of the node    // and compute the height difference.if it is > 1 we will return false    // hashtable to maintain height of each node to reduce the no of redundant    // height computations    static Hashtable<TreeNode, Integer> haTab = new Hashtable<>();    static int height(TreeNode root) {        // if the node is null then it returns the height as -1        int heightOfNode;        if (root == null) {            return -1;        }        if (haTab.containsKey(root)) {            return haTab.get(root);        }        int leftHeight, rightHeight;        leftHeight = height(root.left);        rightHeight = height(root.right);        // finds the height of left subtree and right subtree and returns        // the max of both + 1        heightOfNode = Math.max(leftHeight, rightHeight) + 1;        haTab.put(root, heightOfNode);        return heightOfNode;    }    public static boolean isBalanced(TreeNode root) {        if (root == null) {            return true;        }        int leftHeight, rightHeight;        leftHeight = height(root.left);        rightHeight = height(root.right);        // if left child and right child are balanced and the difference in        // their heights is < 2        // then it is balanced        if (isBalanced(root.left) && isBalanced(root.right)                && Math.abs(leftHeight - rightHeight) < 2) {            return true;        }        return false;    }    public static void main(String[] args) {        TreeNode root = new TreeNode(1);        root.left = new TreeNode(-2);        root.right = new TreeNode(-3);        root.left.left = new TreeNode(1);        root.left.right = new TreeNode(3);        root.right.right = new TreeNode(-1);        System.out.println(isBalanced(root));    }}
Verify that a binary tree is balanced
java;tree