logo CodeStepByStep logo

Main Page → Exercises → Java → Solve an Exercise

numUniqueBSTs

Language/Type: Java binary trees BSTs
Related Links:

Write a method named numUniqueBSTs that accepts a maximum integer value N as a parameter and returns a count of how many "structurally unique" binary search trees (BSTs) can be made using the values 1 through N inclusive. For example, the call of numUniqueBSTs(3) should return 5 because there are 5 unique BSTs containing the values from 1 to 3: 

1       1       2       3       3
 \       \     / \     /       /
  2       3   1   3   1       2
   \     /             \     /
    3   2               2   1

As another example, the call of numUniqueBSTs(4) should return 14 because there are 14 unique BSTs containing the values from 1 to 4: 

(1 / (2 / (3 / (4))))
(1 / (2 / (4 (3))))
(1 / (3 (2) (4)))
(1 / (4 (3 (2))))
(1 / (4 (2 / (3))))
(2 (1) (3 / (4)))
(2 (1) (4 (3)))
(3 (2 (1)) (4))
(3 (1 / (2)) (4))
(4 (3 (2 (1))))
(4 (3 (1 / (2))))
(4 (2 (1) (3)))
(4 (1 / (2 / (3))))
(4 (1 / (3 (2))))

If the value of N passed is 0 or negative, return 0. You may use loops and/or recursion in your solution.

Method: Write a Java method as described, not a complete program or class.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.