270. Closest Binary Search Tree Value

Binary search. We should note that for BST to find place for a new node to insert, we must reach a NULL pointer. So the termination for binary search in BST is either the left or the right child node that we are ready to move to becomes NULL. We only need to compare the root node with the closest node in its subtree in order to get the right one.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int closestValue(TreeNode* root, double target) {  
13:      int a = root->val;  
14:      TreeNode *child = target < a ? root->left : root->right;  
15:      if (child == NULL) return a;  
16:      int b = closestValue(child, target);  
17:      return abs(a - target) < abs(b - target) ? a : b;  
18:    }  
19:  };