Count Balanced Binary Trees of Height h

Problem Statement

Given a height h, count the number of balanced binary trees possible with height h. A balanced binary tree is one where for every node, the difference between heights of the left and right subtrees is at most 1.

Example:

• Input: h = 2
• Output: 3 (The three trees: left subtree height 1 + right height 1, left height 1 + right height 2, left height 2 + right height 1 — but actually: both children height 1 gives 1 tree, one child height 1 and other height 0 gives 2 trees = total 3)

Noob-Friendly Explanation

Think of building a family tree where each person can have a left child and a right child. The "height" tells you how many generations there are. The rule is: for every person, the number of generations on their left side and right side can differ by at most 1. How many different family trees can you make with exactly h generations?

Approach 1: Brute Force

Intuition

A tree of height h has subtrees of height at most h-1. For a balanced tree, both subtrees must have height h-1 or one has h-1 and the other has h-2. Use recursion to count all valid combinations.

Algorithm

1. Base case: height 0 or 1 has 1 tree each.
2. For height h, count trees where both subtrees have height h-1, and trees where one subtree has height h-1 and the other h-2.
3. Total = count(h-1) * count(h-1) + 2 * count(h-1) * count(h-2).

class Solution {
    static final int MOD = 1_000_000_007;

    public static long countBrute(int h) {
        if (h == 0 || h == 1) return 1;

        long leftRight_same = (countBrute(h - 1) % MOD * countBrute(h - 1) % MOD) % MOD;
        long leftRight_diff = (2 * (countBrute(h - 1) % MOD) % MOD * (countBrute(h - 2) % MOD)) % MOD;

        return (leftRight_same + leftRight_diff) % MOD;
    }

    public static void main(String[] args) {
        System.out.println(countBrute(2)); // Output: 3
        System.out.println(countBrute(3)); // Output: 15
    }
}

Complexity Analysis

• Time Complexity: O(2^h) - exponential due to overlapping subproblems
• Space Complexity: O(h) - recursion stack depth

Approach 2: Optimal

Intuition

Use dynamic programming to store the count of balanced trees for each height. Build up from height 0 to h, using the recurrence relation from the brute force approach.

Algorithm

1. Create a dp array where dp[i] = number of balanced binary trees of height i.
2. dp[0] = 1, dp[1] = 1.
3. For each height i from 2 to h: dp[i] = dp[i-1] * dp[i-1] + 2 * dp[i-1] * dp[i-2].
4. Return dp[h].

class Solution {
    static final int MOD = 1_000_000_007;

    public static long countBalancedTrees(int h) {
        if (h == 0 || h == 1) return 1;

        long[] dp = new long[h + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= h; i++) {
            // Both subtrees same height: dp[i-1] * dp[i-1]
            // One subtree h-1, other h-2 (2 ways to assign): 2 * dp[i-1] * dp[i-2]
            long sameHeight = (dp[i - 1] * dp[i - 1]) % MOD;
            long diffHeight = (2 * dp[i - 1] % MOD * dp[i - 2]) % MOD;
            dp[i] = (sameHeight + diffHeight) % MOD;
        }

        return dp[h];
    }

    public static void main(String[] args) {
        System.out.println(countBalancedTrees(2)); // Output: 3
        System.out.println(countBalancedTrees(3)); // Output: 15
    }
}

Complexity Analysis

• Time Complexity: O(h) - single loop from 2 to h
• Space Complexity: O(h) - the dp array