Balanced Binary Tree

Problem

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.

Solution

Top-Down Recursion: O(n^2) time

public class Solution {

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int left = depth(root.left);
        int right = depth(root.right);
        return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode node) {
        if (node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        return Math.max(left, right) + 1;
    }
}

Bottom-Up Recursion: O(n) time

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1;
    }

    private int helper(TreeNode node) {
        if (node == null) return 0;
        int left = helper(node.left);
        if (left == -1) return -1;
        int right = helper(node.right);
        if (right == -1) return -1;
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1; //use + 1 to record the current depth
    }
}

Analysis

A typical Tree Traversal problem solved in recursion
In the top-down solution, we get the depth of left and right subtrees
Then we check if their difference is <=1 then we move to it's left and right subtrees and do the same thing
The problem there is that when we are checking the root we already traversal the subtrees
Therefore, there are some repeated works in top-down solution and the runtime is O(n^2)

In the bottom-up solution, however, run time becomes O(n)
This is become we first get the depth of bottom left and right subtree
If we find they are not balanced, we will return -1
Otherwise, we return the depth by doing Math.max(left, right) + 1
This avoid duplicated checks in the subtrees hence the runtime is O(n)