Introduction
The Balanced Binary Tree Counter problem is a Dynamic Programming problem based on Binary Trees.
In this problem, we are given an integer h, representing the height of a binary tree. Our task is to count the number of different balanced binary tree structures that can be formed with that height.
Before solving the problem, let's understand two important concepts.
What Is a Binary Tree?
A Binary Tree is a hierarchical data structure in which each node can have at most two children:
Left child
Right child
What Is a Balanced Binary Tree?
A Balanced Binary Tree is a binary tree in which the difference between the heights of the left and right subtrees of every node is at most 1.
Mathematically:
|Height(Left) - Height(Right)| <= 1For this problem, we consider:
Height of an empty tree = 0
Height of a single-node tree = 1
Our goal is to calculate the number of distinct balanced binary tree structures for a given height h.
Understanding the Problem with Examples
Let's understand the possible balanced binary trees for different heights.
Example 1: Height = 0
An empty tree has exactly one possible structure.
Output: 1Example 2: Height = 1
Only one structure is possible: a single root node.
Output: 1Example 3: Height = 2
Three different structures are possible:
Root with only a left child
Root with only a right child
Root with both left and right children
Output: 3Example 4: Height = 3
For height 3, there are 15 different balanced binary tree structures.
Output: 15These examples show that the number of balanced binary trees increases quickly as the height increases.
Generating every possible tree individually would be inefficient. Instead, we can use Dynamic Programming.
Understanding the Dynamic Programming Approach
Dynamic Programming is a technique in which we solve a larger problem using previously calculated smaller subproblems.
For this problem, we define:
dp[h] = Number of balanced binary trees of height exactly hTo calculate the answer for height h, we need the results for the previous two heights.
Deriving the Recurrence Relation
For a balanced binary tree of height h, at least one subtree must have height h - 1.
There are two possible cases.
Case 1: Both Subtrees Have Height h - 1
The left subtree has height h - 1, and the right subtree also has height h - 1.
The number of combinations is:
dp[h - 1] * dp[h - 1]or:
dp[h - 1]^2Case 2: One Subtree Has Height h - 1 and the Other Has Height h - 2
There are two possible arrangements:
Left subtree has height
h - 1, right subtree has heighth - 2Left subtree has height
h - 2, right subtree has heighth - 1
The number of combinations is:
2 * dp[h - 1] * dp[h - 2]Combining both cases, we get the recurrence relation:
dp[h] = dp[h - 1]^2 + 2 * dp[h - 1] * dp[h - 2]This is the main formula used to solve the problem.
Base Conditions
Before calculating the recurrence, we need two initial values.
Height | Number of Balanced Trees |
|---|---|
0 | 1 |
1 | 1 |
Why Is dp[0] = 1?
An empty tree is considered one valid structure. This helps us correctly calculate combinations for larger heights.
Why Is dp[1] = 1?
A tree with height 1 contains only one root node.
Therefore:
dp[0] = 1;
dp[1] = 1;Java Implementation
Let's implement the solution using an optimized Dynamic Programming approach.
class Solution {
public int countBT(int h) {
int mod = 1000000007;
// Base conditions
if (h == 0) return 1;
if (h == 1) return 1;
// Previous two results
long a = 1; // Height 0
long b = 1; // Height 1
// Calculate results from height 2 to h
for (int i = 2; i <= h; i++) {
// Apply recurrence relation
long c = (b * b + 2 * b * a) % mod;
// Update previous values
a = b;
b = c;
}
return (int) b;
}
}Line-by-Line Code Explanation
Let's understand how the implementation works.
Step 1: Declare the Modulo Value
int mod = 1000000007;The number of possible balanced binary trees increases rapidly.
Therefore, the problem requires us to return the answer modulo 10^9 + 7.

Join the conversation! Your thoughts help the community grow.