Statement:

You should implement a function that takes as argument a positive number N. Consider all the possible binary search trees having N distinct keys labeled from 1 to N. Find all their preorder traversals and print them in lexicografical order.

Desired solution

Solve the problem in O(output) time using O(N) memory.

Source: https://csacademy.com/contest/interview-archive/task/all-bst-preorders/statement/