The number of full binary trees where each node is the product of its children

A full binary tree is a special type of binary tree in which all parent nodes either have two child nodes or no child nodes. In data structures, these types of trees are considered to be balanced and organized representations. A complete binary tree may have the unique characteristic that each parent node is the product of its child nodes.

In this article, we will discuss different ways to calculate the number of complete binary trees using C so that each node is the product of its children.

Input and output scenarios

For example, in the array {1, 5, 3, 4}, we have only four single nodes 1 (1 x 1), 5 (1 x 5), 3 (1 x 3) and 4 (1 x 4 ).

Input: arr = {1, 5, 3, 4}
Output: 4

In the given array, using all multiples of each element less than the maximum value, if there are multiples in the array, we can create a complete binary tree. Therefore, we find the maximum value in the array.

We start by finding such a binary tree by iterating from the minimum value to the maximum value, since we know that smaller values ​​may be multiples of larger values ​​in the array.

Use dynamic programming

Here, we use dynamic programming to find the number of full binary trees such that each node is the product of its children. We iterate over the array elements and find possible trees that satisfy the above conditions. We store these solutions in dp vectors.

• First, we find the maximum and minimum values ​​in an array using the INT_MAX and INT_MIN constants defined in in C header. Update the maximum and minimum values ​​by iterating the for loop.

• Next, we have a nested loop in which we iterate from the minimum value to the maximum value of the array. In this loop, we check if the dp vector is non-zero.

• If the dp vector is non-zero, then we run another for loop for multiples of j starting from (j j) until the maximum value. For each multiple, we check if there is more than one.

• If there are multiple, then the number of possible full binary trees is equal to the number of arr[j] full binary trees and arr[j]/k.

• We add the currently updated dp value modulo 1000000007 to the result to prevent data overflow.

Example

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

int numOfFullBinaryTrees(int arr[], int N) {
   int minValue = INT_MAX;
   int maxValue = INT_MIN;

   // Find the maximum and minimum value from the array
   for (int j = 0; j < N; j++) {
      minValue = min(minValue, arr[j]);
      maxValue = max(maxValue, arr[j]);
   }

   vector < int > dp(maxValue + 1, 0);

   // One possible full binary tree for each element 
   // in case of single nodes
   for (int j = 0; j < N; j++) {
      dp[arr[j]] = 1;
   }

   int result = 0;
   for (int j = minValue; j <= maxValue; j++) {
      if (dp[j] != 0) {
         for (int k = j + j; k <= maxValue && (k / j) <= j; k += j) {
            if (dp[k] != 0) {
               dp[k] += (dp[j] * dp[k / j]);
               // Check if left child may become right child and vice versa
               if (j != (k / j)) {
                  dp[k] += (dp[j] * dp[k / j]);
               }
            }
         }
         result = (result + dp[j]) % 1000000007;
      }
   }
   return result;
}

int main() {
   int array[] = {12, 3, 5, 6};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Number of full binary trees satisfying the condition are: " << numOfFullBinaryTrees(array, N) << endl;
   return 0;
}

Output

Number of full binary trees satisfying the condition are: 4

Note- Here, the time complexity of the program is O(N^2).

in conclusion

We have discussed how to find the number of full binary trees such that each node is the product of its own children. We solve this problem using a dynamic approach by storing the solutions to the subproblems in dp vectors. We can use a simple nested for loop to iterate from the minimum to the maximum value of the array and check the possible number of complete binary trees with the desired properties.

The above is the detailed content of The number of full binary trees where each node is the product of its children. For more information, please follow other related articles on the PHP Chinese website!