Table of Contents

ExplanationImplementation

Explanation

The crucial observation here is that the answer for nn nodes is the nnth Catalan number.

Proof

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

class Solution {
  public:
	long long nCr(int n, int k) {
		long long res = 1;


		// since C(n, k) = C(n, n - k)
		if (k > n - k) { k = n - k; }


		for (int i = 0; i < k; i++) {
			res *= (n - i);

Java

class Solution {
	public int numTrees(int n) { return (int)(nCr(2 * n, n) / (long)(n + 1)); }


	public long nCr(int n, int k) {
		long res = 1;


		// since C(n, k) = C(n, n - k)
		if (k > n - k) { k = n - k; }


		for (int i = 0; i < k; i++) {

Python

import math




class Solution:
	def numTrees(self, n: int) -> int:
		res = math.comb(2 * n, n) // (n + 1)
		return res

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum