Lecture Notes: Unique Binary Search Trees (LeetCode 96)

Introduction

• Problem: Given an integer n, determine the number of unique binary search trees (BSTs) that can be formed using integers 1 to n.
• Example: For n = 3, the problem asks how many unique BSTs can be formed.

Base Cases

• n = 1: Only one BST possible with a single node.
• n = 2: Two possible BSTs:
  • Root 1: Node 1 as root, node 2 as right child.
  • Root 2: Node 2 as root, node 1 as left child.

General Case for Three Nodes (n = 3)

• If 1 is the root:
  • Subtree consists of nodes 2 and 3 in the right subtree.
  • Possible configurations:
    • Root 2 → Node 3 as right child.
    • Root 3 → Node 2 as left child.
• If 2 is the root:
  • Node 1 on the left, node 3 on the right.
• If 3 is the root:
  • Nodes 1 and 2 must be in the left subtree.
  • Possible configurations:
    • Root 1 → Node 2 as right child.
    • Root 2 → Node 1 as left child.

Recursive and Combinatorial Approach

• Recognize that the problem can be broken down recursively.
• Each node can be the root, leading to subproblems for left and right subtrees.
  • Calculate possible BSTs for left and right subtrees.
  • Multiply counts of left and right subtree configurations to get total count for each root.
• Recursion leads naturally to a dynamic programming solution.

Dynamic Programming Solution

• Time Complexity: O(n^2) due to nested loops for each root node.
• Space Complexity: O(n) for storing results of subproblems in a dp array.

Code Explanation

• Initialize a dp array with size n+1, set base cases for 0 and 1 nodes.
• Loop through each possible number of nodes (from 2 to n):
  • For each node count, consider each node position as the root.
  • Calculate number of trees for left and right subtrees:
    • Left subtree size: root - 1.
    • Right subtree size: total nodes - root.
  • Update dp array with sum of products (left subtree count * right subtree count).*

Conclusion

• Return the result stored for n nodes, which is the final answer.

The lecture covered the approach to solving the unique binary search trees problem using dynamic programming, highlighting the recursive substructure and emphasizing the importance of understanding base cases and subproblem solutions.