Java  

Number of BSTs From Array

Problem Summary

You are given an array of distinct elements.

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

  • How many unique Binary Search Trees (BSTs) can be formed using all elements?

Return an array where each index stores that count.

Key Insight

In a BST:

  • All smaller elements go to the left subtree

  • All greater elements go to the right subtree

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):

  • Sort the array

The position (index) of each element determines:

  • L = number of elements on the left

  • R = number of elements on the right

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

  • L = i

  • R = n - i - 1

Number of BSTs:

  • Catalan(L) × Catalan(R)

Catalan Numbers

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

  • C(0) = 1

  • C(1) = 1

  • C(2) = 2

  • C(3) = 5

  • C(4) = 14

  • C(5) = 42

Formula:

  • C(n) = Σ C(i) × C(n - i - 1)

Example Walkthrough

Input:

arr = [2, 1, 3]

Step 1: Sort

[1, 2, 3]

Step 2: Compute using index

  • Element: 1

    • Index: 0

    • L: 0

    • R: 2

    • Result: 1 × 2 = 2

  • Element: 2

    • Index: 1

    • L: 1

    • R: 1

    • Result: 1 × 1 = 1

  • Element: 3

    • Index: 2

    • L: 2

    • R: 0

    • Result: 2 × 1 = 2

Step 3: Map back to original order

Original array:

[2, 1, 3]

Output:

[1, 2, 2]

Algorithm

  • Clone and sort the array

  • Precompute Catalan numbers up to n

  • For each element in the sorted array:

    • Compute L and R using index

    • Calculate Catalan(L) × Catalan(R)

    • Store results in a map

  • Build final result using original array order

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

  • Time Complexity:

    • Catalan computation → O(n²)

    • Sorting → O(n log n)

    • Overall: O(n²) (n ≤ 6, so very small)

  • Space Complexity: O(n)

Key Takeaways

  • BST structure depends only on node count, not values

  • Sorting helps determine left/right subtree sizes

  • This is a direct application of Catalan numbers

  • Very important pattern for advanced interviews

Pattern Recognition

If a problem involves:

  • Counting BSTs

  • Unique structures

  • Splitting into left & right

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.

Membership not found