25/180: How to determine if a binary tree is Height Balanced

Navneet Ojha
Apr 12, 2021

--

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

  1. Left subtree of T is balanced
  2. Right subtree of T is balanced
  3. 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.
  4. 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.

--

--

Navneet Ojha
Navneet Ojha

Written by Navneet Ojha

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.

No responses yet