LeetCode 823 - Binary Trees With Factors

The problem asks us to determine the number of distinct binary trees that can be constructed from a given array of unique integers, where each integer is strictly greater than 1.

leetcodemediumarrayhash-tabledynamic-programmingsorting

LeetCode Problem 823

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem asks us to determine the number of distinct binary trees that can be constructed from a given array of unique integers, where each integer is strictly greater than 1. The key constraint is that for every non-leaf node in the tree, its value must equal the product of its two children. Leaf nodes can be any value from the array.

The input, arr, is a list of unique integers, each between 2 and 10^9, and the length of arr is at most 1000. The output is an integer representing the number of valid binary trees, modulo 10^9 + 7, because the number of trees can grow very large.

Important observations include that each element can serve as a leaf (single-node tree) and that multiple combinations of factors from the array can form the same product. A naive brute-force approach that attempts to recursively build all trees would quickly become infeasible due to the combinatorial explosion. Edge cases to consider include arrays of length 1 (only one tree), arrays with prime numbers (trees cannot have children except leaves), and arrays containing numbers that are products of multiple array elements.

Approaches

A brute-force approach would attempt to recursively generate all trees for each element in the array by considering all possible pairs of children that multiply to the element’s value. While correct, this approach is extremely inefficient because it explores an exponential number of tree combinations and would quickly exceed time limits for larger arrays.

The optimal solution leverages dynamic programming and hash maps. First, the array is sorted. Then, for each element, we consider it as a potential root. We iterate through all smaller elements to check if they are factors of the current root. If arr[i] % arr[j] == 0 and the quotient arr[i] / arr[j] also exists in the array, we know we can form trees with arr[i] as the root and arr[j] and the quotient as children. Using a hash map to store the number of trees for each value allows us to compute the number of trees for larger elements incrementally, ensuring an O(n^2) solution instead of exponential time.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively build all trees; impractical for n ~ 1000
Optimal O(n^2) O(n) Sort array, use DP and hashmap to count trees efficiently

Algorithm Walkthrough

  1. Sort the input array to ensure we always consider smaller elements first. This ensures that when computing trees for arr[i], all potential factors arr[j] have already been processed.
  2. Initialize a hash map dp where dp[x] stores the number of binary trees with x as the root.
  3. Iterate through each element arr[i]. Initially, set dp[arr[i]] = 1 because every element can form a single-node tree.
  4. For each arr[i], iterate through all arr[j] such that arr[j] < arr[i]. If arr[i] % arr[j] == 0 and the quotient arr[i] / arr[j] exists in the hash map, increment dp[arr[i]] by dp[arr[j]] * dp[arr[i] / arr[j]]. This counts all trees formed by combining valid child pairs.
  5. Sum all values in dp modulo 10^9 + 7 to obtain the final answer.

Why it works: Sorting ensures that all potential factors are already counted. Using a hash map allows O(1) lookup for the existence of factors and the number of trees rooted at those factors. The multiplication accounts for all combinations of left and right subtrees for each factor pair.

Python Solution

from typing import List

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        dp = {}
        arr_set = set(arr)
        
        for x in arr:
            dp[x] = 1
            for y in arr:
                if y >= x:
                    break
                if x % y == 0 and (x // y) in arr_set:
                    dp[x] += dp[y] * dp[x // y]
                    dp[x] %= MOD
        
        return sum(dp.values()) % MOD

The implementation sorts the array first and initializes dp with a count of 1 for each element to account for single-node trees. The nested loop iterates through smaller elements to find valid factor pairs, and the hash map allows quick existence checks. The modulo operation ensures the result fits within integer limits.

Go Solution

func numFactoredBinaryTrees(arr []int) int {
    const MOD = 1_000_000_007
    n := len(arr)
    sort.Ints(arr)
    dp := make(map[int]int)
    arrSet := make(map[int]bool)
    for _, x := range arr {
        arrSet[x] = true
    }
    
    for _, x := range arr {
        dp[x] = 1
        for _, y := range arr {
            if y >= x {
                break
            }
            if x%y == 0 {
                if _, exists := arrSet[x/y]; exists {
                    dp[x] = (dp[x] + dp[y]*dp[x/y]) % MOD
                }
            }
        }
    }
    
    result := 0
    for _, count := range dp {
        result = (result + count) % MOD
    }
    return result
}

The Go version mirrors the Python implementation. Go requires explicit modulo operations and integer maps. Sorting and the hash map setup are similar, ensuring the algorithm's correctness.

Worked Examples

Example 1: arr = [2,4]

Sort: [2,4]

Initialize dp = {}

  • x = 2: dp[2] = 1 (single-node tree)

  • x = 4: dp[4] = 1

  • Check y = 2: 4 % 2 == 0, 4/2 = 2 exists → dp[4] += dp[2]*dp[2] = 1 + 1*1 = 2

Sum: 1 (for 2) + 2 (for 4) = 3

Example 2: arr = [2,4,5,10]

Sort: [2,4,5,10]

Initialize dp = {}

  • x = 2: dp[2] = 1

  • x = 4: dp[4] = 1

  • y = 2: 4 % 2 == 0, 4/2 = 2 exists → dp[4] = 1 + 1*1 = 2

  • x = 5: dp[5] = 1 (no valid factors)

  • x = 10: dp[10] = 1

  • y = 2: 10 % 2 == 0, 10/2 = 5 exists → dp[10] = 1 + 1*1 = 2

  • y = 5: 10 % 5 == 0, 10/5 = 2 exists → dp[10] = 2 + 1*1 = 3

Sum: 1 + 2 + 1 + 3 = 7

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each element is paired with smaller elements, and factor existence check is O(1) via hash map
Space O(n) Hash maps store count for each element and existence lookup

The O(n^2) time arises from nested iteration over the sorted array. Space complexity is linear because only counts for each element are stored, not all possible trees explicitly.

Test Cases

# Provided examples
assert Solution().numFactoredBinaryTrees([2,4]) == 3  # single-node trees + [4,2,2]
assert Solution().numFactoredBinaryTrees([2,4,5,10]) == 7  # includes combinations for 4 and 10

# Edge cases
assert Solution().numFactoredBinaryTrees([2]) == 1  # only one single-node tree
assert Solution().numFactoredBinaryTrees([2,3,6]) == 5  # [2],[3],[6],[6,2,3],[6,3,2]
assert Solution().numFactoredBinaryTrees([2,4,8]) == 7  # [2],[4],[8],[4,2,2],[8,2,4],[8,4,2],[8,2,2,2]

# Stress test
assert Solution().numFactoredBinaryTrees(list(range(2, 10))) > 0  # sanity check for small array
Test Why
[2,4] Checks basic factor pair logic
[2,4,5,10] Multiple factor combinations for one element
[2] Minimal input
[2,3,6] Non-trivial factor pair, multiple possibilities
[2,4,8] Checks recursive factor combinations