Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 3: Count of Structurally Unique Binary Search Trees (hard)

Problem Statement

Given a number ‘n’, write a function to return the count of structurally unique Binary Search Trees (BST) that can store values 1 to ‘n’.

Example 1:

Input: 2
Output: 2
Explanation: As we saw in the previous problem, there are 2 unique BSTs storing numbers from 1-2.

Example 2:

Input: 3
Output: 5
Explanation: There will be 5 unique BSTs that can store numbers from 1 to 3.

Constraints:

  • 1 <= n <= 8

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

SeungJin Kim

· 4 years ago

Why is the space complexity for non memoized version 2^N? It appears to me that the space required is used by the recursion call stack which is at most the depth of n - 1?

Show 1 reply
D

Dylan Asoh

· 4 years ago

time limit exceeded on leetcode

cogom

cogom

· 3 years ago

Could you please explain further why it is O(N^2) time complexity when we use memoization? Thank you!

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago


class Solution:
  def countTrees(self, n):
    
    def solve(start, end):
      if start > end:
        return 1
        
      count = 0 
      
      for i in range(start, end + 1):
        lefts = solve(start, i - 1)
        rights = solve(i + 1, end)

        count += lefts * rights
      
      return count

    return solve(1, n)