[4.1] Balanced Tree ?

1.Example

A balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root
by more than one.

The idea is the difference of min depth and max depth should not exceed 1.


http://www.stoimen.com/blog/2012/06/22/computer-algorithms-binary-search-tree-data-structure/


2. Implementation

private static int maxDepth(TreeNode root)
{
     // Base case
     if(root == null)
        return 0;
     return 1 + Math.max( maxDepth(root.left), maxDepth(root.right) );
}
private static int minDepth(TreeNode root)
{
     // Base case 
     if (root == null)
       return 0;
     return 1 + Math.max( minDepth(root.left), minDepth(root.right) );
}
public static boolean isBalanced(TreeNode root)
{
    return ( (maxDepth(root) - minDepth(root) ) <=1 );
}

3. Similar Ones