Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Problem Challenge 2: Structurally Unique Binary Search Trees

Problem Statement

Given a number n, write a function to return all structurally unique Binary Search Trees (BST) that can store values 1 to n?

Example 1:

Input: 2
Output: List containing root nodes of all structurally unique BSTs.
Explanation: Here are the 2 structurally unique BSTs storing all numbers from 1 to 2:

Example 2:

Input: 3
Output: List containing root nodes of all structurally unique BSTs.
Explanation: Here are the 5 structurally unique BSTs storing all numbers from 1 to 3:

Constraints:

  • 1 <= n <= 19

.....

.....

.....

Like the course? Get enrolled and start learning!
Renat Zamaletdinov

Renat Zamaletdinov

· 2 years ago

It's not required to reconstruct cached data as we only use them either as left or right child without breaking any relationships between parent-to-child nodes.

Should not it be "better" than the provided solution?

#class TreeNode:
#  def __init__(self, val):
#    self.val = val
#    self.left = None
#    self.right = None

class Solution:
  def findUniqueTrees(self, n):
    if n == 0:
      return []

    cache = {}

    def dp(start, end):
      if start > end:
        return [None]

      pair = (start, end)

      if pair not in cache:
        res = []

        for i in range(start, end + 1):
          left = dp(start, i - 1)
          right = dp(i + 1, end)

          for l in left:
            for r in right:
              root = TreeNode(i)
              root.left