Closest Neighbor in BST

 Given a binary search tree and a number N, find the greatest number in the binary search tree that is less than or equal to N. 

                                 

                                       5

                               /      \

                            2        12

                          /   \       /   \

                       1     4    9    20

                                         /   \

                                      19   25

Example 1 :

Input : N = 23
Output : 20
Explanation : The greatest element in the tree which 
              is less than or equal to 23, is 20. 
              (Searching will be like 5->12->20)

 

Example 2 :

Input : N = 5
Output : 4
Explanation : The greatest element in the tree which 
              is less than or equal to 5, is 4. 
              (Searching will be like 5->2->4)

method  :

c++ implementation:

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

    printInorder(node->left); 
  
    v.push_back(node->key); 
  
    printInorder(node->right); 
} 

int findMaxForN(Node* root, int N)
{
    int c=-1;
   
    vector<int>::iterator i;
    printInorder(root);
    
for(i=v.begin();i!=v.end();i++)
{ 
    if(*i<=N)
    c= *i;
} 
 return c;   
}

Time Complexity: O(n) 

space Complexity: O(n) 

here n is the height of the tree.