96. Unique Binary Search Trees

Stanislav Gumeniuk included in leetcode leetcode-problem

2020.06.24 236 words 2 minutes

Contents

Problem

Given n, how many structurally unique (BST) that store values 1 … n?

example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution

Dynamic programming

Main idea - dynamic programming :

We know that unique bst for n=1 is 1, for n=0 is 1, for n=2 is 2. Also, we know than for n=3 : {1,2,3} we can check tries with:

root 1 – its mean that we should check tries right with nodes {2,3}
root 2 – its mean that we should check tries left with nodes {2} and right with nodes {3}
root 3 – its mean that we should check tries left with nodes {1,2}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func numTrees(n int) int {
    a:= make(map[int]int, 0)
    a[0] = 1
    a[1] = 1
    a[2] = 2
    return helper(n , a)
}

func helper(n int, a map[int]int) int {
    if _, ok := a[n]; ok {
        return a[n]
    }
    res := 0
    for idx := 0; idx<n; idx++ {
        res += (helper(idx, a)*helper(n-idx-1, a))
    }

    a[n] = res

    return a[n]  
}