Search A BST For First Occurrence Of k

来源：EPI

原帖：EPI 11.4

题目：
Given a BST T, write recursive and iterative versions of a function that takes a BST T, a key k, and returns the node containing k that would appear first in an inorder walk. If k is absent, return null. For example, when applied to the BST in Figure 11.2 on the following page, your algorithm should return Node B if k = 108, Node G if k = 285, and null if k = 143.

代码：

 struct TreeNode {  
     int data;  
     TreeNode* left;  
     TreeNode* right;  
     TreeNode(int d) : data(d), left(NULL), right(NULL) {}  
 };  
   
 //Version 1: recursion  
 TreeNode* find_first_equal_k(TreeNode* r, int k) {  
     if (!r) {  
         return NULL; // no match  
     } else if (r->data == k) {  
         // Recursively search the left subtree for first one == k  
         TreeNode* n = find_first_equal_k(r->left, k);  
         return n ? n : r;  
     }   
     // Search left or right tree according to r->data and k  
     return find_first_equal_k(r->data < k ? r->right : r->left, k);  
 }  
   
 // Version 2: iteration  
 TreeNode* find_first_equal_k(TreeNode* r, int k) {  
     while (r) {  
         if (r->data < k) {  
             r = r->right;  
         } else if (r->data > k) {  
             r = r->left;  
         } else { // r->data == k  
             // Search for the leftmost in the left subtree  
             TreeNode* l = r->left;  
             while (l && l->data == k) {  
                 r = l;  
                 l = l->left;  
             }  
             return r;  
         }  
     }  
     return NULL; // not match  
 }