Solution: Problem Challenge 2: Structurally Unique Binary Search Trees

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 2: Structurally Unique Binary Search Trees

Table of Contents

Contents are not accessible

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

Solution

This problem follows the Subsets pattern and is quite similar to Evaluate Expression. Following a similar approach, we can iterate from 1 to ‘n’ and consider each number as the root of a tree. All smaller numbers will make up the left sub-tree and bigger numbers will make up the right sub-tree. We will make recursive calls for the left and right sub-trees

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

The time complexity of this algorithm will be exponential and will be similar to Balanced Parentheses. Estimated time complexity will be $O(n*2^n)$ but the actual time complexity $(O(4^n/\sqrt{n})$ is bounded by the Catalan number and is beyond the scope of a coding interview. See more details here.

Space Complexity

The space complexity of this algorithm will be exponential too, estimated at $O(2^n)$ , but the actual will be $(O(4^n/\sqrt{n})$ .

Memoized version

Since our algorithm has overlapping subproblems, can we use memoization to improve it? We could, but every time we return the result of a subproblem from the cache, we have to clone the result list because these trees will be used as the left or right child of a tree. This cloning is equivalent to reconstructing the trees; therefore, the overall time complexity of the memoized algorithm will also be the same.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible