You are given an integer N >2. How many distinct pre-order traversals are there for all possible BSTs that store integers 1...N in ascending order?
Follow-up: How many distinct post-order traversals are there ?

Hint #1:
What kind of traversals can help you reconstruct any binary tree?

Hint #2:
What is common to all the binary search trees described in the problem statement?