1, 2, …, n, each used exactly once: for every node, all values in its left subtree are smaller and all values in its right subtree are larger than its own.
Return how many different search trees can be built this way. Two trees differ if their shape or the value at some position differs.n=2 → 2
The root is either 1 (with 2 as its right child) or 2 (with 1 as its left child). Two shapes.
n=4 → 14
Roots 1, 2, 3 and 4 give 5 + 2 + 2 + 5 = 14 trees, since the subtrees left and right of the root are built independently.
n=1 → 1
n=2
2
Run checks the first 3 tests in your browser. Submit checks all 17 tests on the server, hidden ones included.