I want to write a program in c++. In the input, in first line, two integers N(number of nodes) and P(destination node) are given. Then, in second line, those N nodes are given.

These nodes are elements of a Binary Search Tree(BST). As we know, in BST, every node has at most 2 children and every node is greater than its left child and smaller than its right child.

The output of this program has 2 lines. In the fist line, I have to print the number of all possible paths to reach to P. P is definitely at the last leaf of the tree. (I mean it’s external).

And in the second line, I should print one of those paths.

For example:

Input:

4 50

10 60 20 30

Output:

4

10 20 30 60

Well, for the second line of the output, the idea I have in mind is to just print the ascendingly sorted array of nodes given in input because it’d be definitely a path to reach to P.

But I have some issues for calculating the number of all paths for the first line of input. In this example, 4 BSTs exist that in them 50 is the last leaf:

1- 10 20 30 60

2- 10 20 60 30

3- 10 60 20 30

4- 60 10 20 30

So the number of paths is 4. But how should I implement this in code? I mean how should I find all the possible BSTs with these nodes in a way that P is external and then, how should I count the paths to reach to it?