Domain 2MediumMEDIUM

Binary Trees With Factors

Count valid binary trees where root value equals product of children using DP on sorted array.

Domain: medium•Updated: 2026-09-01
#dynamic programming#hash map#O(N^2)#O(N)

Problem Breakdown

We are given an array arr containing unique integers greater than 1. We need to construct binary trees such that every non-leaf node’s value is the product of its children’s values. The goal is to count all possible valid binary trees using elements from arr.

Key constraints:

  • Node Values: Must be present in arr (can reuse numbers).
  • Structure: Root = Left Child × Right Child. Single nodes are always valid trees.
  • Output: Total count modulo 109+710^9 + 7.

Intuition

A brute-force recursive approach is inefficient due to overlapping subproblems and the exponential growth of tree structures. We can optimize using Dynamic Programming (DP).

State Definition: Let dp[v] be the number of valid binary trees rooted with value v.

  • Base Case: Every element in arr forms at least one single-node tree, so initially dp[x] = 1 for all x∈arrx \in arr.
  • Transition: For a root root, if it has children left and right such that left * right == root, then the number of ways to form this specific structure is dp[left] * dp[right]. Since binary trees distinguish left/right, both permutations (a,b)(a,b) and (b,a)(b,a) count as distinct structures unless a=ba=b.
  • Order: To ensure we have computed DP values for all potential children before computing the parent, we must process numbers in increasing order. This guarantees that when calculating dp[root], any valid factor (child) has already been processed.

Approach

  1. Sort the input array arr to handle dependencies from smallest factors to largest roots.
  2. Initialize a hash map (dp) where each key is an element of arr and value starts at 1 (representing the single-node tree).
  3. Iterate through each number in the sorted array as a potential root node:
    • For every previous number in the array, check if it divides the current root evenly.
    • If divisible (root % prev == 0), calculate other = root // prev.
    • Check if other exists in our DP map (which implies it is a valid element from arr).
    • Add dp[prev] * dp[other] to the current count for root, applying modulo at each step.
  4. Sum all values in the dp map and return the result modulo 109+710^9 + 7.

Complexity Analysis

  • Time: Sorting takes O(Nlog⁡N)O(N \log N). The nested loop iterates through pairs of elements, resulting in O(N2)O(N^2) operations. Given N=1000N=1000, this is approximately 5×1055 \times 10^5 iterations, which fits well within time limits for Python (≈107−108\approx 10^7-10^8 ops/sec).
  • Space: We store DP counts and existence checks in a hash map. Space Complexity: O(N)O(N).

Solution

class Solution:
    def numFactoredBinaryTrees(self, arr):
        MOD = 10**9 + 7
        
        # Sort array to process smaller factors first (bottom-up DP)
        arr.sort()
        
        # Map value -> count of trees rooted at that value. 
        # Initialize all with 1 because every number can be a single-node tree itself.
        dp = {x: 1 for x in arr}
        
        # Iterate through each element as the potential root node
        for i, num in enumerate(arr):
            # Check against all previous elements to find valid left children
            for j in range(i):
                prev = arr[j]
                
                # If 'prev' divides 'num', check if the other factor exists
                if num % prev == 0:
                    other = num // prev
                    
                    # Since we sorted, any valid child must be smaller than root. 
                    # We only need to ensure 'other' is actually in our input set (and thus has a DP count).
                    if other in dp:
                        # Add combinations of trees from left and right children
                        # Note: The loop structure handles distinct pairs naturally by checking every prev as potential Left Child.
                        # If we find valid pair (prev, other), it contributes to 'num'.
                        # Since binary tree order matters (Left vs Right):
                        # When j points to a specific factor A and B is the complement:
                        # We add dp[A] * dp[B]. 
                        # Later in this same outer loop iteration? No.
                        # If we find valid pair (A, B) where both exist in arr:
                        # Case 1: A < B. When j points to index of A, other=B exists -> add dp[A]*dp[B].
                        # Case 2: B > A is covered by the fact that if B also divides num and appears earlier (B < num), 
                        # then when j points to B, other=A exists -> add dp[B]*dp[A].
                        
                        count = (dp[prev] * dp[other]) % MOD
                        dp[num] = (dp[num] + count) % MOD
                        
        return sum(dp.values()) % MOD

Edge Cases Handled

  • Single Element Array: The loop runs once, inner loop doesn’t run. Returns 1 (correct).
  • No Factors Found: If a number is prime relative to the array elements provided, it remains at base count of 1. Summation handles this correctly.
  • Perfect Square Roots: E.g., arr = [2, 4]. For root 4: factor pair (2, 2). Loop checks prev=2, calculates other=2. Since 2 is in map, adds dp[2]*dp[2]. This counts the single structural tree [4; 2, 2] once.
  • Large Values: Modulo arithmetic applied at every addition step to prevent integer overflow and meet return requirement (though Python handles large ints automatically).