Leetcode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Understand the problem:
The problem asks for determining if a tree is height-balanced. Note that the height-balanced binary tree is defined as the depth of the two subtress of every node never differ by more than 1. 

Solution:
The basic idea of this problem is very similar to the path sum problem, which we can still employ the preorder traversal. The difference is we can maintain two variable, min and max, and update them when we reach to a leaf node. If we found that the difference between max and min is greater than one, it indicates that the tree is not height-balanced. 

Wrong Answer:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int min = Integer.MAX_VALUE;
    private int max = Integer.MIN_VALUE;
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        
        // the cornor case where the tree has no left or right subtrees
        if (root.left == null || root.right == null) {
            min = 1;
            max = 1;
        }
        return preOrderTraversal(root, 0);
    }
    
    private boolean preOrderTraversal(TreeNode root, int depth) {
        if (root == null) return true;
        
        depth++;
        // if it is leaf
        if (root.left == null && root.right == null) {
            if (depth < min) min = depth;
            if (depth > max) max = depth;
            
            if ((max - min) > 1) return false;
        }
        
        if (preOrderTraversal(root.left, depth) == false) return false;
        if (preOrderTraversal(root.right, depth) == false) return false;
        
        return true;
    }
}

Why the solution is wrong? Consider the following case:
                  1
                 /   \
               2    2
              /        \
            3          3
           /              \
          4               4 
For the solution above, it will falsely think of the tree is balanced. However is not. 
Let's go back to the definition of the balanced tree. The height of a binary tree is defined as the number of nodes from the current node to the deepest leaf. Note the difference between the depth and height of a tree. The depth of a tree is the number of nodes from root to the current node.  So for a height-balanced tree, for a node, both its left subtree and right subtree should be balanced. In the example above, the node 2 on the left is not height-balanced, since its left height is 3, while the right is 1. 

Correct Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        
        if (getHeight(root) == -1) return false;
        
        return true;
    }
    
    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        
        if (left == -1 || right == -1) return -1;
        
        if (Math.abs(left - right) > 1) return -1;
        
        return Math.max(left, right) + 1;
    }
}

So we can see that the correct solution used post-order traversal. We used post-order traversal because we got the height bottom-up. 


Update 9/30/14:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return isBalancedHelper(root) != -1;
    }
    
    private int isBalancedHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = isBalancedHelper(root.left);
        int right = isBalancedHelper(root.right);
        
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        
        return Math.max(left, right) + 1;
    }
}

Update on 4/30/19:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) {
        // write your code here
        if (root == null) {
            return true;
        }
        
        ResultType ans = isBalancedHelper(root);
        
        return ans.balanced;
    }
    
    private ResultType isBalancedHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, true);
        }
        
        ResultType left = isBalancedHelper(root.left);
        ResultType right = isBalancedHelper(root.right);
        
        int depth = Math.max(left.depth, right.depth) + 1;
        boolean balanced = left.balanced && right.balanced && Math.abs(left.depth - right.depth) <= 1;
        ResultType ans = new ResultType(depth, balanced);
        
        return ans;
    }
}

class ResultType {
    int depth;
    boolean balanced;
    
    public ResultType(int depth, boolean balanced) {
        this.depth = depth;
        this.balanced = balanced;
    }
}