Binary Trees With Factors

Binary Trees With Factors

What is this problem about?

This coding problem asks you to find the number of unique binary trees you can build using an array of unique integers. Each node in the tree must have a value from the array, and if a node has children, the value of the node must be equal to the product of its children's values. You can use each integer from the array as many times as you like.

Why is this asked in interviews?

Google frequently uses this problem to test a candidate's ability to identify subproblems within a complex scenario. It’s a perfect candidate for Dynamic Programming (DP) because the number of ways to form a tree with root $X$ depends directly on the number of ways to form trees with roots $A$ and $B$, where $A imes B = X$. It tests your ability to handle sorting, counting, and potentially large results (requiring modulo arithmetic).

Algorithmic pattern used

This problem uses Dynamic Programming (DP) and Sorting. First, sort the array. This ensures that when you process a number, you've already calculated the results for all its possible factors (which must be smaller). Use a Map to store dp[x], the number of ways to form a tree with root x. For each x, iterate through all smaller numbers y in the array. If x % y == 0 and x / y is also in the array, then dp[x] += dp[y] * dp[x / y].

Example explanation

Array: [2, 4, 8]

1. dp[2] = 1 (just the node 2).
2. For 4:
   • Possible factors: (2, 2).
   • dp[4] = 1 (node 4 itself) + dp[2] * dp[2] = 1 + 1 = 2.
3. For 8:
   • Possible factors: (2, 4) and (4, 2).
   • dp[8] = 1 (node 8 itself) + dp[2] * dp[4] + dp[4] * dp[2] = 1 + 2 + 2 = 5. Total trees = 1 + 2 + 5 = 8.

Common mistakes candidates make

One frequent mistake is forgetting to add the "single node" case (the +1 in the DP formula). Another is failing to account for the fact that if $A imes B = X$, you can have $A$ as the left child and $B$ as the right, or vice versa (unless $A=B$). Also, many candidates forget to apply the modulo $10^9 + 7$ at each addition, leading to overflow issues.

Interview preparation tip

When you see a problem where a solution for a number depends on solutions for its factors or smaller parts, think about sorting and DP. Sorting is a powerful preprocessing step that often reveals the order in which you should solve subproblems.