Binary Trees With Factors: Counting Factor Trees with DP

Given an array of unique integers where each integer is strictly greater than 1, you can use them as tree nodes to build binary trees. The rule: every non-leaf node's value must equal the product of its two children's values. Each array element can be used as many times as needed. How many such binary trees can you form? Return the count modulo 10^9 + 7.

This is LeetCode 823: Binary Trees With Factors, and it is a great example of how sorting and dynamic programming work together. The key insight is that you can build bigger trees from smaller ones, and a hash map lets you look up factor pairs efficiently.

Why this problem clicks once you see the pattern

At first glance, this problem feels like it might need recursion or some kind of tree-building simulation. But the constraint that every parent equals the product of its children means larger values can only appear above smaller values in any valid tree. That ordering is the hint that sorting the array and processing values from smallest to largest will let you build on previously computed results.

For each value val, you ask: "Which pairs of values in my array multiply to give val?" For every such pair (a, b) where a * b = val, the number of new trees rooted at val is dp[a] * dp[b]. You multiply because every tree rooted at a can pair with every tree rooted at b independently.

This is the same "build from smaller subproblems" idea behind problems like Unique Binary Search Trees, but here the subproblem relationship comes from multiplication rather than range splitting.

The approach

1. Sort the array so you always process smaller factors before larger values.
2. Store every value in a set (or hash map) for O(1) lookups.
3. Initialize dp[val] = 1 for every value (the single-node tree).
4. For each value val, iterate through all values j in the array where j is less than val. If val is divisible by j and val / j also exists in the array, then dp[val] += dp[j] * dp[val / j].
5. Sum all dp[val] values and return the result modulo 10^9 + 7.

def numFactoredBinaryTrees(arr):
    MOD = 10**9 + 7
    arr.sort()
    dp = {}
    for val in arr:
        dp[val] = 1
        for j in arr:
            if j >= val:
                break
            if val % j == 0 and val // j in dp:
                dp[val] = (dp[val] + dp[j] * dp[val // j]) % MOD
    return sum(dp.values()) % MOD

The nested loop looks like it could be O(n^2), and it is. But with n capped at 1000 in the constraints, that is perfectly fine. The hash map lookup for val // j is O(1), so the total work per value scales with the number of elements smaller than it.

Walking through the algorithm

Let's trace through arr = [2, 4, 5, 10] step by step.

The multiplication dp[a] * dp[b] is the heart of this problem. It reflects the fact that binary trees have two independent subtrees. If there are 3 ways to build the left subtree and 2 ways to build the right subtree, that gives 6 combinations total. This is the same counting principle you see in Unique Binary Search Trees, where the total for a root is the product of left and right subtree counts.

Complexity analysis

Where n is the length of the array. The DP approach processes each value once and, for each value, checks all smaller values as potential factors. The hash map uses O(n) space to store factor lookups and DP counts.

The building blocks

Sorted order enables DP

Many DP problems require you to process elements in a specific order so that subproblems are already solved when you need them. Here, sorting guarantees that when you reach a value like 10, you have already computed dp[2] and dp[5]. This is the same principle behind Longest Increasing Subsequence, where you process elements left to right and build on earlier results.

Hash map for factor lookups

The hash map serves two purposes: checking whether a potential factor exists in the array (O(1) instead of scanning) and storing the DP count for each value. This dual role is common in DP problems where the state space is not a contiguous range of integers. Instead of a DP array indexed by position, you use a DP dictionary indexed by value.

Edge cases to watch for

• All primes: e.g., arr = [2, 3, 5, 7]. No value is the product of two others, so every value contributes exactly 1 tree. The answer is just the length of the array.
• Perfect squares: e.g., arr = [2, 4] where 4 = 2 * 2. Both children are the same value, and that is fine. dp[4] = 1 + dp[2] * dp[2] = 2.
• Chain of factors: e.g., arr = [2, 4, 8]. The value 8 can use (2, 4) and (4, 2) as children. Since dp[4] = 2 (one single-node tree plus the 4->2,2 tree), dp[8] benefits from the compounding: dp[8] = 1 + dp[2]*dp[4] + dp[4]*dp[2] = 1 + 2 + 2 = 5.
• Single element: arr = [7]. Only one tree is possible, the node 7 by itself. Return 1.

From understanding to recall

You can probably follow the walkthrough above and see why the algorithm works. But could you write the solution from memory next week? The gap between "I understand it" and "I can produce it on demand" is real, and it trips people up in interviews.

Spaced repetition closes that gap. You revisit this problem at increasing intervals, write the sorted DP with hash map approach from scratch each time, and after a few reps the pattern becomes automatic. The "sort, initialize dp to 1, check all factor pairs, multiply subtree counts" template sticks with you.

This pattern, DP on sorted values with factor relationships, is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Unique Binary Search Trees - Another tree-counting DP problem where you multiply left and right subtree counts
• House Robber - A classic intro to DP with a decision at each step, showing how smaller subproblems feed into larger ones
• Coin Change - Bottom-up DP on sorted values, same "build from previously solved subproblems" pattern

Counting trees where parent equals child product is a satisfying problem because the DP recurrence maps so directly to the tree structure. Once you see that dp[val] accumulates products of factor-pair counts, the whole solution follows naturally.