# Find closest value in BST

###### tags:`Binary search tree` `Easy`

## Problem

### Sample

<br>

## Solutions

### Official

<br>

---

### Everyone's

<br>

:::spoiler 東

/* 
Time O(log(n)) | Space O(1); when input is a balance BST
Time O(n) | Space O(1); when input is a linear BST
n is the total amount of nodes of the input tre
*/
function findClosestValueInBst(tree, target) {
  let closestVal = tree.value;
  let currMinDist = Math.abs(target-closestVal);
  let currNode = tree;
  while(currNode){
    if(Math.abs(currNode.value - target) < currMinDist){
      currMinDist = Math.abs(currNode.value-target);
      closestVal = currNode.value;
    }
    if(currNode.value < target) currNode = currNode.right;
    else if(currNode.value > target) currNode = currNode.left;
    else return target;
  }
  return closestVal;
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity is O(N), Space complexity is O(1)
 */

const diff = (a, b) => typeof a === 'number' && typeof b === 'number' ? Math.abs(a - b) : Number.POSITIVE_INFINITY;

function findClosestValueInBst(tree, target, closestValue) {
  const newClosestValue = diff(tree.value, target) < diff(closestValue, target) ? tree.value : closestValue;

  const searchDirection = target < tree.value ? 'left' : 'right';
    
  if (!tree[searchDirection]) return newClosestValue;
  else return findClosestValueInBst(tree[searchDirection], target, newClosestValue);
}

:::

<br>

:::spoiler YC

/*
    time: O(log(n)) - where n is the number of nodes in the tree
    space: O(1)
*/

function findClosestValueInBst(tree, target) {
  let closestValue = tree.value;
  let currNode = tree;
  while(currNode){
    const closestDiff = Math.abs(closestValue - target);
    const currDiff = Math.abs(currNode.value - target);
    if (closestDiff > currDiff){
      closestValue = currNode.value;
    }

    if (target > currNode.value){
      currNode = currNode.right;
    } else if (target < currNode.value){
      currNode = currNode.left;
    } else {
      break;
    }
  }
  return closestValue;
}

:::

---

## Supplement / Discussion