An empty tree is height balanced. A non empty binary tree T is balanced if

- Left subtree of T is balanced
- Right subtree of T is balanced
- The difference between heights of left subtree and right subtree is not more than one. This above height balancing scheme is used in AVL trees.
- Get height of right and left tree. return true if difference between height is not more than one.

class BinaryTree{

Node root;

boolean isBalanced(Node node){

int lh;

int rh;

if(node == null)

return true;

lh = heigh(node.left);

rh = height(node.right); if(Math.abs(lh -rh)<= 1 && isBalanced(node.left) && isBalanced(node.right))

return true;

return false; }

int height(Node node){

if(node == null)

return 0;return 1+Math.max(height(node.left), height(node.right)); }}

Time complexity. O(n²) worst case, occurs in case of skewed trees.

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.