25/180: How to determine if a binary tree is Height Balanced
Apr 12, 2021
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.