What is the time complexity of Unique Binary Search Trees?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Unique Binary Search Trees?

This problem uses Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Unique Binary Search Trees?

Insight 1: The problem can be solved using dynamic programming. The number of BSTs for 'n' nodes can be computed by considering each node from 1 to 'n' as the root and combining the number of possible left and right subtrees. Insight 2: The number of BSTs with 'i' nodes can be expressed recursively as the sum of (number of left subtrees with 'j' nodes) * (number of right subtrees with 'i-1-j' nodes), where 'j' ranges from 0 to i-1.

Which companies ask LeetCode 96. Unique Binary Search Trees in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Clari and 7 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Unique Binary Search Trees - LeetCode 96 Solution

Q: How to solve Unique Binary Search Trees?

The provided code uses dynamic programming to calculate the number of unique BSTs. It builds a DP table 'dp' where dp[i] stores the number of unique BSTs with 'i' nodes. The algorithm iterates from 1 to 'n', and for each 'i', it considers each node from 1 to 'i' as the root. For each root 'j', it multiplies the number of unique left subtrees (with 'j-1' nodes, represented by dp[j-1]) with the number of unique right subtrees (with 'i-j' nodes, represented by dp[i-j]). Summing up these products for all possible roots 'j' gives the total number of unique BSTs for 'i' nodes.

Unique Binary Search Trees - Complete Solution Guide

Unique Binary Search Trees is LeetCode problem 96, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer n , return the number of structurally unique BST' s (binary search trees) which has exactly n nodes of unique values from 1 to n . Example 1: Input: n = 3 Output: 5 Example 2: Input: n = 1 Output: 1 Constraints: 1 <= n <= 19

Detailed Explanation

The problem asks us to find the number of structurally unique Binary Search Trees (BSTs) that can be formed using 'n' distinct nodes labeled from 1 to 'n'. A BST is a binary tree where for each node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value. The 'structurally unique' part means we're counting trees that have different shapes, even if they contain the same values but arranged differently.

Solution Approach

The provided code uses dynamic programming to calculate the number of unique BSTs. It builds a DP table 'dp' where dp[i] stores the number of unique BSTs with 'i' nodes. The algorithm iterates from 1 to 'n', and for each 'i', it considers each node from 1 to 'i' as the root. For each root 'j', it multiplies the number of unique left subtrees (with 'j-1' nodes, represented by dp[j-1]) with the number of unique right subtrees (with 'i-j' nodes, represented by dp[i-j]). Summing up these products for all possible roots 'j' gives the total number of unique BSTs for 'i' nodes.

Step-by-Step Algorithm

Step 1: Initialize a DP array 'dp' of size (n+1) with all values set to 0. dp[i] will store the number of unique BSTs with i nodes.
Step 2: Set the base case: dp[0] = 1. An empty tree (0 nodes) is considered one unique BST.
Step 3: Iterate from i = 1 to n (inclusive). This loop calculates dp[i] for each i.
Step 4: Inside the outer loop, iterate from j = 0 to i-1 (inclusive). This loop considers each node j+1 as the root of the BST.
Step 5: For each j, update dp[i] by adding dp[j] * dp[i - 1 - j]. dp[j] represents the number of unique left subtrees with j nodes, and dp[i - 1 - j] represents the number of unique right subtrees with i-1-j nodes. The '-1' accounts for the root node.
Step 6: After the outer loop completes, dp[n] will contain the number of unique BSTs with n nodes. Return dp[n].

Key Insights

Insight 1: The problem can be solved using dynamic programming. The number of BSTs for 'n' nodes can be computed by considering each node from 1 to 'n' as the root and combining the number of possible left and right subtrees.
Insight 2: The number of BSTs with 'i' nodes can be expressed recursively as the sum of (number of left subtrees with 'j' nodes) * (number of right subtrees with 'i-1-j' nodes), where 'j' ranges from 0 to i-1.
Insight 3: The base case is when n = 0 or n = 1, where there is only 1 possible BST (an empty tree or a single-node tree).

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Clari, Microsoft, Samsung, Snap, TikTok, Tower Research Capital, Yahoo, Zoho.

Unique Binary Search Trees | LeetCode 96

Medium

Math Dynamic Programming Tree Binary Search Tree Binary Tree

Time: O(n^2)Space: O(n)

Solution Code

Available in:

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        
        return dp[n];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 96: Unique Binary Search Trees - Detailed explanation and solution approaches.

Topics

Math Dynamic Programming Tree Binary Search Tree Binary Tree

Companies

AdobeAmazonAppleBloombergClariMicrosoftSamsungSnap

Stats

Difficulty:Medium

Languages:4

Companies:12

Problem #:96

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a DP array 'dp' of size (n+1) with all values set to 0. dp[i] will store the number of unique BSTs with i nodes.
2
Step 2: Set the base case: dp[0] = 1. An empty tree (0 nodes) is considered one unique BST.
3
Step 3: Iterate from i = 1 to n (inclusive). This loop calculates dp[i] for each i.
4
Step 4: Inside the outer loop, iterate from j = 0 to i-1 (inclusive). This loop considers each node j+1 as the root of the BST.
5
Step 5: For each j, update dp[i] by adding dp[j] * dp[i - 1 - j]. dp[j] represents the number of unique left subtrees with j nodes, and dp[i - 1 - j] represents the number of unique right subtrees with i-1-j nodes. The '-1' accounts for the root node.
6
Step 6: After the outer loop completes, dp[n] will contain the number of unique BSTs with n nodes. Return dp[n].

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The algorithm has two nested loops. The outer loop iterates from 1 to n, and the inner loop iterates from 0 to i-1. Therefore, the time complexity is proportional to the sum of 1 + 2 + ... + n, which is O(n^2). The space complexity is O(n) because we use a DP array of size n+1 to store the intermediate results.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Catalan Number Formula

The number of unique BSTs is actually a Catalan number, given by the formula C(n) = (2n)! / ((n+1)! * n!). We can directly compute this using the formula.

Time: O(n) or O(n^2) depending on the implementation of factorial calculation.Space: O(1) if factorial is computed iteratively and only the final result is stored, otherwise O(n) if precomputed factorials are stored.

Trade-offs: The Catalan number formula provides a more direct solution, but calculating factorials can be computationally expensive, especially for larger 'n'. If the factorial function is optimized (e.g., using precomputed factorials), it might be slightly faster than the dynamic programming approach. However, the DP approach is generally easier to understand and implement, and avoids potential overflow issues if factorials get too large.

✨

Key Insights

1Insight 1: The problem can be solved using dynamic programming. The number of BSTs for 'n' nodes can be computed by considering each node from 1 to 'n' as the root and combining the number of possible left and right subtrees.
2Insight 2: The number of BSTs with 'i' nodes can be expressed recursively as the sum of (number of left subtrees with 'j' nodes) * (number of right subtrees with 'i-1-j' nodes), where 'j' ranges from 0 to i-1.
3Insight 3: The base case is when n = 0 or n = 1, where there is only 1 possible BST (an empty tree or a single-node tree).

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: n = 0. The code correctly handles this case by initializing dp[0] = 1, which means there's one possible BST (the empty tree).
Edge case 2: n = 1. The code correctly calculates dp[1] as dp[0] * dp[0] = 1 * 1 = 1, representing the single-node tree.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not initializing the base case dp[0] = 1. This is crucial for the recursion to work correctly, as it provides the starting point for building larger BSTs.

✗Common mistake 2: Incorrectly calculating the indices for the left and right subtrees in the inner loop. It's important to remember that the root takes up one node, so the remaining nodes are split between the left and right subtrees, and the index calculations need to reflect that.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Compiler design. BSTs are used to represent the structure of expressions in programming languages. Knowing the number of possible BSTs can be useful in analyzing the complexity and potential ambiguities in parsing these expressions.

🏦Real-world scenario 2: Data structure optimization. Understanding the number of possible tree structures can help in designing more efficient data structures. For example, in databases, knowing how many different ways data can be organized in a tree-like structure can aid in optimizing query performance.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 5, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Unique Binary Search Trees"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?