Number of Ways to Reorder Array to Get Same BST

Number of Ways to Reorder Array to Get Same BST - Problem

Array Math Divide and Conquer Dynamic Programming Tree Union Find Binary Search Tree Memoization Combinatorics Binary Tree Hard

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.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3]

› Output: 2

💡 Note: Root 2 must come first. Left subtree has [1], right has [3]. Valid arrangements: [2,1,3] and [2,3,1] both build the same BST structure.

Example 2 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Only one element, so only one possible arrangement that builds the BST.

Example 3 — Linear Tree

$ Input: nums = [3,1,2]

› Output: 1

💡 Note: Forms a tree where 3 is root, 1 is left child, 2 is right child of 1. Only one valid arrangement maintains this structure.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ nums.length
All integers in nums are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [2,1,3] to build BST

Build BST

Construct BST: 2 as root, 1 left, 3 right

Count Arrangements

Find all arrangements that build same BST: [2,1,3], [2,3,1]

Key Takeaway

🎯 Key Insight: Root must appear first, then left/right subtrees can be interleaved using combinatorics

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that for any BST, the root must appear first, then left and right subtree elements can be interleaved in C(left_size + right_size, left_size) ways. Best approach uses recursive combinatorics to count arrangements without generating them. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Permutations	O(n! × n)	O(n)	Generate all permutations and check which ones build the same BST
Recursive with Memoization	O(n²)	O(n)	Use recursion to count arrangements of left and right subtrees with memoization

Generate All Permutations — Algorithm Steps

Generate all permutations of the array
Build BST from each permutation
Compare each BST with original BST
Count matching BSTs

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with [2,1,3]

Generate Permutations

Create all 6 possible arrangements

Check Each

Build BST from each and compare with original

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* buildBST(int* arr, int n) {
    if (n == 0) return NULL;
    struct TreeNode* root = createNode(arr[0]);
    for (int i = 1; i < n; i++) {
        struct TreeNode* curr = root;
        while (1) {
            if (arr[i] < curr->val) {
                if (curr->left) {
                    curr = curr->left;
                } else {
                    curr->left = createNode(arr[i]);
                    break;
                }
            } else {
                if (curr->right) {
                    curr = curr->right;
                } else {
                    curr->right = createNode(arr[i]);
                    break;
                }
            }
        }
    }
    return root;
}

int treesEqual(struct TreeNode* t1, struct TreeNode* t2) {
    if (!t1 && !t2) return 1;
    if (!t1 || !t2) return 0;
    return t1->val == t2->val && treesEqual(t1->left, t2->left) && treesEqual(t1->right, t2->right);
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int permute(int* nums, int n, int start, struct TreeNode* originalBST) {
    if (start == n) {
        return treesEqual(buildBST(nums, n), originalBST) ? 1 : 0;
    }
    
    int count = 0;
    for (int i = start; i < n; i++) {
        swap(&nums[start], &nums[i]);
        count += permute(nums, n, start + 1, originalBST);
        swap(&nums[start], &nums[i]);
    }
    return count;
}

int solution(int* nums, int n) {
    struct TreeNode* originalBST = buildBST(nums, n);
    return permute(nums, n, 0, originalBST) % MOD;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int nums[50];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, each taking O(n) time to build and compare BST

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing permutation and BST nodes

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler