09/04/2017

[Java] Find if a binary tree is balanced

A binary tree is balanced if the left and right branches do not differ in depth for more than one level.

Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:

 /*  
   is tree balanced  
   A tree is balanced if the left and right branches do not differ for more than 1 level in length  
   */  
   private static Entry isTreeBalancedAux(BST root){  
     //null root is always balanced  
     if(root == null) return new Entry(true, -1);  
   
     Entry left, right;  
   
     //check subtrees  
     left = isTreeBalancedAux(root.left);  
     right = isTreeBalancedAux(root.right);  
   
     //if they are not balanced, we have our answer  
     if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);  
   
     //otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced  
     if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);  
   
     //finally, if all is good, return the max depth from this node incuding itself and mark it as balanced  
     return new Entry(true, Math.max(left.height, right.height) + 1);  
   }  
   
   public static boolean isTreeBalanced(BST root){  
     return isTreeBalancedAux(root).isBalanced;  
   }  


I use an additional data structure (Entry) to pass around two pieces of information:

- is the tree balanced so far
- what is the current depth of the path being analyzed

No comments:

Post a Comment

With great power comes great responsibility