Alg.23 Find Closest Value In BST

From algoexpert.io

Write a function to find the closest value of the target number in a BST. Here is an example:



The BST structure:

static class BST {
  public int value;
  public BST left;
  public BST right;

  public BST(int value) {
    this.value = value;
  }
}

There are 2 ways: recursion and iteration. They both complete in O(logn) time, the difference between them is the space complexity, since the recursion way needs to use call stack, its time complexity is O(logn)(average) or O(n)(worst) while the iteration way performs O(1) in space. Here is the iteration way:

public static int findClosestValueInBst(BST tree, int target) {
    // If we initialize the closest value with MAX/MIN value of integer,
    // there may exist problems!
    BST current = tree;
    int closest = current.value;
    int closestDiff = Math.abs(closest - target);
    while (current != null) {
        if (Math.abs(current.value - target) < closestDiff) {
            closest = current.value;
            closestDiff = Math.abs(closest - target);
        }
        
        if (current.value > target) {
            current = current.left;
        } else if (current.value < target) {
            current = current.right;
        } else break;
    }
    
    return closest;
}

Time complexity: average: O(logn), worst: O(n);

Space complexity: O(1).

public static int findClosestValueInBst(BST tree, int target) {
  return helper(tree, target, tree.value);
}
  
public static int helper(BST tree, int target, int closest) {
    if (Math.abs(tree.value - target) < Math.abs(closest - target)) {
        closest = tree.value;
    } 
  
    if (tree.value > target && tree.left != null) {
        return helper(tree.left, target, closest);
    } 
  
    if (tree.value < target && tree.right != null) {
        return helper(tree.right, target, closest);
    }
  
    return closest;
}

Time complexity: average: O(logn), worst: O(n);

Space complexity: average: O(logn), worst: O(n).

Donate