Search BST For The First Key Larger Than K

来源：EPI

原帖：EPI 11.5

题目：
Write a function that takes a BST T and a key k, and returns the first entry larger than k that would appear in an order walk. If k is absent or no key larger than k is present, return null. For example, when applied to the BST in Figure 11.1 on the previous page you should return 29 if k = 23; if k = 32, your should return null.

代码：

 struct TreeNode {  
   int data;  
   TreeNode* left;  
   TreeNode* right;  
   TreeNode(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
 TreeNode* find_first_larger_k_with_k_exist(TreeNode* r, int k) {  
   bool found_k = false;  
   TreeNode* first = NULL;  
   while (r) {  
     if (r->data == k) {  
       found_k = true;  
       r = r->right;  
     } else if (r->data > k) {  
       first = r;  
       r = r->left;  
     } else { // r->data < k  
       r = r->right;  
     }  
   }  
   return found_k ? first : NULL;  
 }