Count of binary trees, given inorder traversal.

Given an inorder traversal only for a binary tree (not necessarily a BST), give a pseudo code to generate all possible binary trees for this traversal sequence.
Firstly, how many binary trees can be generated given an in-order traversal? I know that given 'n' nodes, number of BTs possible is (2^n)-n. But if we are given a specific in-order sequence, can we cut down on this number?


Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.


If you need to build all those Trees, then there are 3 ways a new node N could be added to the already existing set of Tree(s) T to preserve the inorder sequence.
1. N could be added as the rightmost child of tree T.
2. N could be root and T as its left subtree.
3. The right subtree of T say R could be added as left subtree of N and then N added as the right subtree of T.

Kth Smallest element in Binary Search Tree in O(N) - Recursive and Iterative.

Write a function to take a BST and a value k as input and have it print the kth smallest element in the BST.
Write a function that takes a binary tree as input, and have it perform In order traversal - recursive and then iterative

Output:
97 92 3 10 87 6 46
Printing inorder:
3 6 10 46 87 92 97
K value: 3
Kth Smallest Node Value: 10
Kth Node :10