0110.md

110. Balanced Binary Tree

Level:

Topic:

Question

A binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Input: root = [3,9,20,null,null,15,7]
Output: true

Intuition

Recursive: For every node, compare the height of left subtree and right subtree and differ within 1

Code

Time: O(n log n), height takes O(log n) best case if it's balanced already
Space: O(n)

Recursive

public boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;

    return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int height(TreeNode root) {
    if (root == null)
        return 0;

    return 1 + Math.max(height(root.left), height(root.right));
}