Print encoding for an Array: Rules: consider BST made from given array. Let say number x is present in the BST and to reach x, If you go right print 1, if left then 0.Now you are given an index i in the array A (so x = A[i]) and print the encoding without constructing BST to reach x and without space with least time complexity.

/*    
      ALGORITHM
      1. Scan array from left to right.
      2. Keep 2 variables min = INT_MIN and max = INT_MAX
                min and max are used to keep track of whether the subtree of current node will store desired number searchNumber.
      3. If value of current elements is between min and max, then subtree of this node will contain searchNumber.
      4. If search number is less than current element, then update min = currentElement and print 1  since it will take right path.
      5. If search number is greater than current element then update max = currentElement and print 0, since it will take left path.
     
      COMPLEXITY
      Time  : O(n)
      Space: O(1)
*/

    #include <iostream>
    #include <climits>
   
    using namespace std;
   
    int main()
    {
            int a[]={50,30,10,20,70,60,55,65,63,80};
            int searchNumber = 63;
            int size = sizeof(a)/sizeof(a[0]);
            int min = INT_MIN;
            int max = INT_MAX;
            for(int i=0; i<size && a[i] != searchNumber ; i++)
            {
                 if(a[i] >min && a[i] < max)
                 {
                     if(a[i] < searchNumber)
                     {
                        min = a[i];
                        cout<<" 1";
                     }
                     else
                     {
                         max = a[i];
                         cout<<" 0";
                     }
                 }
            }  
        system("pause");
    }