Check for Height Balanced Tree

Check for Balanced Tree

Given a binary tree, find if it is height balanced or not.
A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree. Expected time complexity is O(n)
Algorithm:
  • Create a class to hold height and isBalanced boolean of a tree
  • Traverse tree in post order
    • If node is null then
      • return height=0 and isBalanced = true
    • If node is leaf node then
      • return height=1 and isBalanced = true
    • Recursively call for left sub tree
    • Recursively call for right sub tree
    • If leftSubTree is balanced and rightSubTree is balanced then
      • return height = Max(leftSubTree.height and leftSubTree.height) + 1 and balanced = true
    • Else
      • return balanced = false and height =0

Latest Source Code:
Github: HeightBalancedTreeChecker.java


Output:

         1               
      / \       
     /   \      
    /     \     
   /       \    
   2       3       
  / \     /     
 /   \   /      
 4   5   6       
/               
7               
                                
Is height balanced : true
----------------------------------------------------------------------
       1               
      / \       
     /   \      
    /     \     
   /       \    
   2       3       
  / \           
 /   \          
 4   5           
/               
7               
                                
Is height balanced : false
Author: Hrishikesh Mishra