Ceil in BST

Given a BST and a number X, find Ceil of X.

Note: Ceil(X) is a number that is either equal to X or is immediately greater than X.

Example 1:

Input:
      5
    /   \
   1     7
    \
     2 
      \
       3
X = 3
Output: 3
Explanation: We find 3 in BST, so ceil
of 3 is 3.

Example 2:

Input:
     10
    /  \
   5    11
  / \ 
 4   7
      \
       8
X = 6
Output: 7
Explanation: We find 7 in BST, so ceil
of 6 is 7.




method  :

c++ implementation:

vector<int>v;
void printInorder(struct Node* node) 
{  
    if (node == NULL) 
        return; 

    printInorder(node->left); 
  
    v.push_back(node->data); 
  
    printInorder(node->right); 
} 
int findCeil(Node* root, int input) 
{ 
    if (root == NULL) 
        return -1; 
  
   while(!v.empty())
    v.pop_back();
    
    vector<int>::iterator i;
    printInorder(root);
  for(i=v.begin();i!=v.end();i++)
  { 
    if(*i>=input)
    {  
      return *i;
    }
  }  
 return -1;   
} 


Time Complexity: O(n) 
space Complexity: O(n) 
darkmode