Dada una secuencia de números, puedes construir el BST (Binary Search Tree) asociado. Entonces, fijado un nodo del árbol que no sea una hoja, si consideras los subárboles izquierdo y derecho, mientras mantengas el orden relativo con los nodos de su subárbol, cualquier orden mantendrá el mismo BST.

En el caso que has puesto, el único nodo que tiene un subárbol a cada lado es el 4. El subárbol izquierdo es un 3 y el derecho un 5 y a continuación un 4. Por lo tanto, el 3, 5, 4 de la entrada lo puedes ordenar como quieras siempre que el 5 vaya antes que el 4, por estar en el mismo subárbol, y así salen las tres posibles opciones (moviendo de sitio el 3).

El cálculo de fijado un nodo cuántas ordenaciones válidas hay lo puedes calcular fácilmente con programación dinámica y seguramente por combinatoria también salga. Lo único que tienes que tener cuidado de no repetir casos.

Lo he pensado rápido así que quizá me haya equivocado en algún punto, pero si es correcto el algoritmo resultante tiene complejidad polinómica y por lo tanto es mucho más eficiente que lo que comentabas.

No tienes que guardar el recorrido, te da igual si sólo quieres saber cuántas ordenaciones hay (no cuáles son), simplemente deberías saber cuántos nodos tiene el subárbol, que lo puedes precalcular linealmente para todos los nodos haciendo un único recorrido inicial del árbol.