Unique Binary Search Trees

1. Problem Description

Given an integer n, determine how many binary search trees can be formed using nodes 1 ... n.

2. Approach

• DFS
  • If k in 1 - n is chosen as the root value, 1 - k-1 forms the left subtree and k+1 - n forms the right subtree.
    • If the left subtree has a possible forms and the right subtree has b, the whole tree has a * b possible forms.
• DFS + memoization
• Dynamic programming

3. Implementation

3.1. DFS

func numTrees(n int) int {
    if n <= 1 {
        return 1
    }
    res := 0
    // Any value in [1,n] can be the root; left-subtree count * right-subtree count gives the number of trees for that root
    // For example, in [1,7], if root is 3, the left side is [1,2] with 3-1=2 elements, and the right side is [4,5,6,7] with 7-3=4 elements
    for i := 1; i <= n ; i++ {
        res += numTrees(i-1) * numTrees(n-i)
    }
    return res
}

3.2. DFS + Memoization

func numTrees(n int) int {
    memo := make(map[int]int, 0)
    return numTreesDFS(n, memo)
}


func numTreesDFS(n int, memo map[int]int) int {
    count, ok := memo[n]
    if ok {
        return count
    }

    if n <= 1 {
        return 1
    }

    count = 0
    for i := 1; i <= n; i++{
        count += numTreesDFS(i-1, memo)*numTreesDFS(n-i, memo)
    }
    memo[n] = count
    return count
}

3.3. Dynamic Programming

package main

func numTrees(n int) int {
	store := []int{1, 1}
	if n <= 1 {
		return store[n]
	}

	for i := 2; i < n+1; i++ {
		s := i-1
		count := 0
		for j := 0; j < i; j++ {
			count += store[j] * store[s-j]
		}
		store = append(store, count)
	}

	return store[n]
}

4. References

• 96. Unique Binary Search Trees - LeetCode
• Unique Binary Search Trees: Recursion, DP, Math - LeetCode