Find closest value in BST

refer to : https://www.algoexpert.io/questions/Find%20Closest%20Value%20In%20BST

Find Closest Value in BST

1. problem statement.

给定一个二叉搜索树和一个目标值，返回这个BST中跟目标值最接近的值closest value，假定只有一个最接近的值。

2. analysis

初始化一个closest value(root.value/Math.max_value)，从根部开始遍历二叉树，计算abs(curr - target) 和 abs(closest - target)，如果abs(curr - target) < abs(closest - target), 更新closest 为 curr. curr为当前节点的值。遍历的同时，比较target和curr的值，if target > curr, 直接去继续遍历curr所在的左子树，if target < curr, 直接去继续遍历curr所在的右子树，如果target == curr, 返回当前的closest。

3. recursive method

# average : O(logn) time | O(logn) space: recursive memory. (balanced BST)
# worst: O(n) time O(n) | space. (one branch BST)

def findClosestValueInBst(tree, target):
    # Write your code here.
    return helper(tree, target, tree.value)

def helper(tree, target, closest):
    if tree is None:
        return closest
    if abs(target-tree.value) < abs(target-closest):
        closest = tree.value
    if target > tree.value:
        return helper(tree.right,  target, closest)
    elif target < tree.value:
        return helper(tree.left, target, closest)
    else:
        return tree.value
        
# This is the class of the input tree. Do not edit.
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

 1 import java.util.*;
 2 
 3 class Program {
 4   public static int findClosestValueInBst(BST tree, int target) {
 5     // Write your code here.
 6     return helper(tree, target, tree.value);
 7   }
 8     
 9     public static int helper(BST tree, int target, int closest){
10         if(Math.abs(target - tree.value) < Math.abs(target - closest)){
11             closest = tree.value;
12         }
13         if(target < tree.value && tree.left != null){
14             return helper(tree.left, target, closest);
15         }else if(target > tree.value && tree.right != null){
16             return helper(tree.right, target, closest);
17       }else{
18             return closest;
19         }
20     }    
21 
22   static class BST {
23     public int value;
24     public BST left;
25     public BST right;
26 
27     public BST(int value) {
28       this.value = value;
29     }
30   }
31 }

4. iterative method

# average : O(logn) time | O(1) space
# worst: O(n) time | O(1) space

省去重复调用helper function的步骤，用currNode追踪当前的节点，省空间。

 1 # average : O(logn) time|O(1) space
 2 # worst: O(n) time O(1)|space
 3 def findClosestValueInBst(tree, target):
 4     # Write your code here.
 5     return helper(tree, target, tree.value)
 6 
 7 def helper(tree, target, closest):
 8     currNode = tree
 9     while currNode is not  None:
10         if abs(target-currNode.value) < abs(target-closest):
11             closest = currNode.value
12         if target > currNode.value:
13             currNode = currNode.right
14         elif target < currNode.value:
15             currNode = currNode.left
16         elif target == currNode.value:
17             break    
18     return closest
19         
20         
21 # This is the class of the input tree. Do not edit.
22 class BST:
23     def __init__(self, value):
24         self.value = value
25         self.left = None
26         self.right = None

 1 import java.util.*;
 2 
 3 class Program {
 4   public static int findClosestValueInBst(BST tree, int target) {
 5     // Write your code here.
 6     return helper(tree, target, tree.value);
 7   }
 8     
 9     public static int helper(BST tree, int target, int closest){
10         BST currNode = tree;
11         while(currNode != null){
12             if(Math.abs(target - currNode.value) < Math.abs(target - closest)){
13                 closest = currNode.value;
14           }
15           if(target < currNode.value){
16               currNode = currNode.left;
17           }else if(target > currNode.value){
18               currNode = currNode.right;
19         }else{
20               break;
21           }
22         }
23         return closest;
24         
25     }    
26 
27   static class BST {
28     public int value;
29     public BST left;
30     public BST right;
31 
32     public BST(int value) {
33       this.value = value;
34     }
35   }
36 }

some tips need to pay attention to.

BST currNode = tree; creat a new BST class and assign the value to tree.

while(currNode != null). don't forget this, and don't need to check currNode.left currNode.right is null or not in inner if statement

else{
             break;      if currNode.value = target, break

    }
outside the while loop, return closest.