We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Reorder Array to Get Same BST

Difficulty: Hard

Problem Description

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

Key Insights

  • The structure of the BST is determined by the order of insertion of elements.
  • To maintain the same BST structure, any reordered array must preserve the relative positions of left and right subtrees.
  • The number of valid reorderings can be calculated using combinatorial mathematics based on the sizes of left and right subtrees.
  • A recursive approach can be employed to compute the number of ways to reorder the array while keeping the BST structure intact.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution involves recursively calculating the number of ways to reorder the elements while maintaining the structure of the BST. The steps include:

  1. Identify the root of the current subtree.
  2. Determine the left and right subtrees based on the root.
  3. Recursively calculate the number of ways to reorder the left and right subtrees.
  4. Use combinatorial math to combine the results from the left and right subtrees, specifically using the binomial coefficient to account for the different ways to interleave elements from both subtrees.

Code Solutions

MOD = 10**9 + 7

def binomial_coefficient(n, k):
    if k > n:
        return 0
    if k == 0 or k == n:
        return 1
    res = 1
    for i in range(1, k + 1):
        res = res * (n - i + 1) % MOD * pow(i, MOD - 2, MOD) % MOD
    return res

def count_ways(nums):
    def count_ways_helper(left, right):
        if left > right:
            return 1
        root = nums[left]
        left_count = 0
        for i in range(left + 1, right + 1):
            if nums[i] < root:
                left_count += 1
        right_count = (right - left) - left_count
        
        left_ways = count_ways_helper(left + 1, left + left_count)
        right_ways = count_ways_helper(left + left_count + 1, right)
        return left_ways * right_ways % MOD * binomial_coefficient(left_count + right_count, left_count) % MOD

    return count_ways_helper(0, len(nums) - 1)

# Example usage:
print(count_ways([2, 1, 3]))  # Output: 1
print(count_ways([3, 4, 5, 1, 2]))  # Output: 5
← Back to All Questions