Balanced Binary Tree

NeetCode: Balanced Binary Tree · LeetCode: 110. Balanced Binary Tree · Difficulty: Easy

A binary tree is height-balanced if, for every node, the heights of its left and right subtrees differ by at most 1. Return whether the tree is balanced.

Example

Text

Input:  [1, 2, 3, null, null, 4]                    Output: true
Input:  [1, 2, null, 3, null, 4]                       Output: false   (left side is 3 deep, right side is empty)

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: compute both heights at every node

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int height(TreeNode node) {
        return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
    }

    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);
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isBalanced(tree(1, 2, 3, null, null, 4)));
        System.out.println(s.isBalanced(tree(1, 2, null, 3, null, 4)));
    }
}

Output

true
false

Time: O(n²) worst case, since height is recomputed at every node. Space: O(h).

Optimal: return the height, or -1 if unbalanced

One DFS computes each subtree's height. If a subtree is already unbalanced, or the current node's two heights differ by more than 1, return -1 right away. Every caller checks for -1 and returns it unchanged, so the failure passes all the way up. A real height is never negative, so -1 cannot be confused with one. Each node is visited once.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    // Returns the height, or -1 if some subtree is unbalanced.
    private int check(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = check(node.left);
        if (left == -1) {
            return -1;
        }
        int right = check(node.right);
        if (right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return 1 + Math.max(left, right);
    }

    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.isBalanced(tree(1, 2, 3, null, null, 4)));
        System.out.println(s.isBalanced(tree(1, 2, null, 3, null, 4)));
        System.out.println(s.isBalanced(tree()));
    }
}

Output

true
false
true

Time: O(n). Space: O(h).