Question:- You are given an array of positive integer. You are required to construct a BST based on following rules:
1. You can choose any element A[i] as root 0 <= i < N
2. If j < i, then A[j] must be in left subtree of the root node
3. If j > i, then A[j] must be in right subtree of the root node
Constraints:
1 <= N <= 10^5
1 <= A[i] <= 10^5
Output: Print Maximum height can be possible
Example:
Given A = [5, 4, 6, 2, 3, 4]
One BST possible is
2
\
3
\
4
Similarly, We can form 2 more BSTs 6 as root. But height of those trees also is 2. So, Output for this is 2.