Skip to main content

Unique Binary Search Trees

Problem statement​

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3Output: 5

Example 2:

Input: n = 1Output: 1

Constraints:

  • 1 <= n <= 19

My solution​

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    let map = new Map();
    return dfs(1, n, map)
};

function dfs(left, right, map) {
    if (left > right) {
        return 1;
    }
    
    if (map.has(`${left}-${right}`)) {
        return map.get(`${left}-${right}`);
    }
    
    let total = 0;
    
    for (let i = left; i <= right; i++) {
        const leftNode = dfs(left, i - 1, map);
        const rightNode = dfs(i + 1, right, map)
        
        total += leftNode * rightNode;
    }
    
    map.set(`${left}-${right}`, total)
    return total;
}