Java – Efficiently find whether Binary Search Tree is Height Balanced or not

binary treecomplexityjava

A binary tree is height balanced if and only if the two subtrees of root are height balanced and the difference between the two subtrees height is at most 1.

I implemented a code in java to find whether a binary search tree is height balanced or not. I did it this way:

Recursively call the function isBalanced(Node) starting with root and the base condition being if node is null return true. But to calculate height of a subtree rooted at Node x, I have to call a separate function getHeight(Node) on that node and use this function to get and compare the height of two subtrees of a node and return a boolean value accordingly.

But this separate function call is making my code inefficient,because in case of skew tree when every node has one child this function will cause my program's time complexity to be O(N^2), N being number of vertices.

What I want to know is is there a way to remove this separate function call and still get the work done, so that I can have a linear time algorithm.

Here is my java code.

class BST
{
 public Node insert(Node x,int key)
 {
     if(x==null)
      return new Node(key,null,null);
     else if(key>x.key)
     {
         x.right=insert(x.right,key);
         return x;
     }
     else if(key<x.key)
     {
         x.left=insert(x.left,key);
         return x;
     }
     else {x.key=key;return x;}
 }
 public boolean isBalanced(Node root)
 {
     if(root==null)
      return true;
     else
     {
         if(isBalanced(root.left)&&isBalanced(root.right))
         {
             if(Math.abs(getHeight(root.left)-getHeight(root.right))<=1)
              return true;
             else return false;
         }
         else return false;
     }
 }
 public int getHeight(Node x)
 {
     return BFS(x,0);
 }
 public int BFS(Node x,int h)
 {
     if(x==null)
      return h;     
     return Math.max(BFS(x.right,h+1),BFS(x.left,h+1));
 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     Node root=null;
     root=tree1.insert(root,14);
     root=tree1.insert(root,16);
     root=tree1.insert(root,5);
     root=tree1.insert(root,3);
     root=tree1.insert(root,12);
     root=tree1.insert(root,10);
     root=tree1.insert(root,13);
     root=tree1.insert(root,20);
     root=tree1.insert(root,18);
     root=tree1.insert(root,23);   
     root=tree1.insert(root,15);
     System.out.println(tree1.isBalanced(root));
 }
}
class Node
{
 Node left,right;
 int key;
 Node(int key,Node left,Node right)
 {
  this.key=key;
  this.left=left;
  this.right=right;
 }
}

I am reposting this question here because I got a no response on Stack Overflow.

Best Answer

If balanced means that the height is at most log_2(number_of_nodes) + 1, I suggest an algorithm could look like this:

# define a tree
tree := null | (left : tree, right : tree)

# check if a tree is balanced
is_balanced(tree) {
    maximum_height, number_of_elements = walk(tree)
    return maximum_height <= 1 + log_with_base_2(number_of_elements) 
}

# walk the tree
walk(tree) {
    if tree is null return 0, 0
    left_height,  left_number_of_elements  = walk(tree.left )
    right_height, right_number_of_elements = walk(tree.right)
    height = 1 + max(left_height, right_height)
    number_of_elements = left_number_of_elements + right_number_of_elements + 1
    return height, number_of_elements
}

The algorithm walks the whole tree once. walk(tree) = O(number_of_nodes(tree)) = O(n).

When testing keep this case in mind:

  x
  |\
  x x
 /| |\
  x x x
     \
      x

The heights of the sub-trees are off by one but the whole tree is not balanced.

Related Topic