Efficiently find whether Binary Search Tree is Height Balanced or not?

Question

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.}

Answer 1

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.

Answer 2

To calculate the height, you have to traverse tree, possibly by using recursion. To check that it is balanced, you have to traverse it exactly the same way. So these ways can probably be combined.

I am tired and can't think of a good name for such a function right now, and I have a feeling the solution is ugly and there is probably a better way. But, it will work.

Say we make a function find_height_and_balance, that returns -1 if the tree isn't balanced, and the tree's height if it is.

Something like:

int find_height_and_balance(node) {
    if (node == null) {
        return 0  // A leaf is balanced and height 0
    }

    int left = find_height_and_balance(node.left)
    if (left == -1) { return -1 }
    int right = find_height_and_balance(node.right)
    if (right == -1) { return -1 }

    if (Math.abs(left - right) > 1) {
        return -1  // The difference in heights is larger than 1
    }

    return max(left, right) + 1 # Return height

(if the function name looks like Python, that's because I wrote Python first and then changed it...)

Edit: Note that your definition of 'balanced' and the test case in User's answer are different; this code checks for your definition, but I think the definition is wrong.