Problem Summary

You are given an array of distinct elements.

For each element arr[i], treat it as the root and determine:

Return an array where each index stores that count.

Key Insight

In a BST:

The structure of a BST depends only on the number of nodes, not the actual values.

Core Idea

Since values don’t matter (only relative order matters):

The position (index) of each element determines:

If an element is at index i in the sorted array:

Number of BSTs:

Catalan Numbers

Catalan numbers represent the number of unique BSTs possible with n nodes.

Formula:

Example Walkthrough

Input:

arr = [2, 1, 3]

Step 1: Sort

[1, 2, 3]

Step 2: Compute using index

Step 3: Map back to original order

Original array:

[2, 1, 3]

Output:

[1, 2, 2]

Algorithm

Java Code

import java.util.*;

class Solution {
    public ArrayList<Integer> countBSTs(int[] arr) {
        int n = arr.length;

        int[] sorted = arr.clone();
        Arrays.sort(sorted);

        // Precompute Catalan numbers
        int[] catalan = new int[n + 1];
        catalan[0] = catalan[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += catalan[j] * catalan[i - j - 1];
            }
        }

        // Map value to result
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int left = i;
            int right = n - i - 1;

            int ways = catalan[left] * catalan[right];
            map.put(sorted[i], ways);
        }

        // Build result in original order
        ArrayList<Integer> result = new ArrayList<>();
        for (int val : arr) {
            result.add(map.get(val));
        }

        return result;
    }
}

Complexity

Key Takeaways

Pattern Recognition

If a problem involves:

Think Catalan Numbers immediately

Summary

This problem demonstrates how Binary Search Tree structures depend purely on the relative positioning of elements rather than their actual values. By sorting the array and leveraging Catalan numbers, we can efficiently compute the number of possible BSTs for each element acting as root. The approach combines combinatorics with indexing logic, making it a classic and important pattern for solving advanced tree and dynamic programming problems.