Check tree is balanced or not
/* Java program to determine if binary tree is
height balanced or not */
/* A binary tree node has data, pointer to left child,
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int d)
{
data = d;
left = right = null;
}
}
// A wrapper class used to modify height across
// recursive calls.
class Height {
int height = 0;
}
class BinaryTree {
Node root;
/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node root, Height height)
{
/* If tree is empty then return true */
if (root == null) {
height.height = 0;
return true;
}
/* Get heights of left and right sub trees */
Height lheight = new Height(), rheight = new Height();
boolean l = isBalanced(root.left, lheight);
boolean r = isBalanced(root.right, rheight);
int lh = lheight.height, rh = rheight.height;
/* Height of current node is max of heights of
left and right subtrees plus 1*/
height.height = (lh > rh ? lh : rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if (abs(lh -rh) >= 2)
return false;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else
return l && r;
}
public static void main(String args[])
{
Height height = new Height();
/* Constructed binary tree is
1
/ \
2 3
/ \ /
4 5 6
/
7 */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(6);
tree.root.left.left.left = new Node(7);
if (tree.isBalanced(tree.root, height))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)